题目链接: https://ac.nowcoder.com/acm/contest/46800/G

题意

你有一个长为n的数组{ai}，你需要支持以下两种操作：

1. 输入l,r,k，对区间[l,r]中所有数字执行ai:=round(10*sqrt(ai))操作k次
2. 输出当前数组所有数字的和。

你需要正确处理m次这样的操作。

(1≤n,m≤1e5, ​0≤ai​≤1e9)

思路

令 f(x) = round(10*sqrt(x)，打表可知 f(x) 在 N+ 上所有的不动点为 {0, 99, 100}，且在 [0, 1e6] 的区间上其余点的迭代周期小于等于 11。

区间修改求和可以使用线段树。但是在这里只需要求整个数组的所有数字和，这样的话就可以用一个 map ，在得到一个区间 [l, r] 时，用 map.lower_bound(l) 可以得到索引大于 l 的一个迭代器，将其迭代到 r 的时候停下来。并且在某个点的值下降到不动点的时候可以用 erase 把它删掉。

复杂度 O(m·logn)。

代码

#include <iostream>
#include <map>
#include <cmath>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int n, m; std::cin >> n >> m;

  std::map<int, int> arr{{n+1, 0}, {0, 0}};
  long long sum = 0;
  orep(i, 1, n+1) {
    int tmp; std::cin >> tmp;
    arr[i] = tmp;
    sum += arr[i];
  }

  orep(i, 0, m) {
    int op; std::cin >> op;
    if (op == 1) {
      int l, r, k; std::cin >> l >> r >> k;
      for(auto it = arr.lower_bound(l); it->first <= r; it++) {
        orep(j, 0, k) {
          int tt = round(10*sqrtl(it->second));
          sum = sum - it->second + tt;
          it->second = tt;
          if (tt == 100 || tt == 0 || tt == 99) { it = arr.erase(it); it--; break; }
        }
      }
    } else {
      std::cout << sum; NL;
    }
  }

  return 0;
}