给出一个长度为 n 的数列A，接下来有 m 次操作，操作有三种： 1.对于所有的i∈[l,r]，将 Ai 变成 Ai+x 。 2.对于所有的 i∈[l,r] ，将 Ai 变成 ⌊Ai−−√⌋ 3.对于所有的 i∈[l,r] ，询问 Ai 的和。
很显然的线段树。 如果只有 1 操作或只有2操作都比较简单，裸的线段树即可。 但如果有两个操作呢？
我么考虑把 Sqrt 操作转化一下，把它转化成最普通的线段树具有的功能，就是区间加法。 %%% tlzmybm _ Evan 大神。 所以加上这个操作好像就差不多了QAQ
if (mx[o] == mn[o] || mx[o] - mn[o] == (int)sqrt(mx[o]) - (int)sqrt(mn[o])) { Add(o, l, r, L, R, (int)sqrt(mn[o]) - mn[o]); return; }所以大概复杂度是 O(nlogn) 的。QAQ根本不会证。 不过还是过掉了。
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> using namespace std; typedef long long ll; inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; char c = get(); int sign = 1; for (; c < '0' || c > '9'; c = get()) if(c == '-') sign = 0; for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + c - '0', c = get()); x = sign ? x : -x; } const int N = 100010; int n, m, opr, x, y, z; int a[N]; ll add[N << 3], sum[N << 3], mx[N << 3], mn[N << 3]; inline void PushDown(int o, int l, int r) { if (!add[o]) return; int mid = (l + r) >> 1; add[o << 1] += add[o]; add[o << 1 | 1] += add[o]; mx[o << 1] += add[o]; mx[o << 1 | 1] += add[o]; mn[o << 1] += add[o]; mn[o << 1 | 1] += add[o]; sum[o << 1] += add[o] * (ll)(mid - l + 1); sum[o << 1 | 1] += add[o] * (ll)(r - mid); add[o] = 0; } inline void PushUp(int o) { sum[o] = sum[o << 1] + sum[o << 1 | 1]; mx[o] = max(mx[o << 1], mx[o << 1 | 1]); mn[o] = min(mn[o << 1], mn[o << 1 | 1]); } void Build(int o, int l, int r) { if (l == r) { sum[o] = mx[o] = mn[o] = a[l]; return; } int mid = (l + r) >> 1; Build(o << 1, l, mid); Build(o << 1 | 1, mid + 1, r); PushUp(o); } void Add(int o, int l, int r, int L, int R, int x) { PushDown(o, l, r); if (L <= l && R >= r) { mn[o] += x; mx[o] += x; add[o] += x; sum[o] += (ll)x * (ll)(r - l + 1); return; } int mid = (l + r) >> 1; if (L <= mid) Add(o << 1, l, mid, L, R, x); if (R > mid) Add(o << 1 | 1, mid + 1, r, L, R, x); PushUp(o); } void Sqrt(int o, int l, int r, int L, int R) { PushDown(o, l, r); if (sum[o] == r - l + 1) return; if (mx[o] == mn[o] || mx[o] - mn[o] == (int)sqrt(mx[o]) - (int)sqrt(mn[o])) { Add(o, l, r, L, R, (int)sqrt(mn[o]) - mn[o]); return; } if (l == r) { sum[o] = mx[o] = mn[o] = sqrt(sum[o]); return; } int mid = (l + r) >> 1; if (L <= mid) Sqrt(o << 1, l, mid, L, R); if (R > mid) Sqrt(o << 1 | 1, mid + 1, r, L, R); PushUp(o); } ll Query(int o, int l, int r, int L, int R) { PushDown(o, l, r); if (L <= l && R >= r) return sum[o]; int mid = (l + r) >> 1; ll res = 0; if (L <= mid) res += Query(o << 1, l, mid, L, R); if (R > mid) res += Query(o << 1 | 1, mid + 1, r, L, R); return res; } int main(void) { read(n); read(m); for (int i = 1; i <= n; i++) read(a[i]); Build(1, 1, n); for (int i = 0; i < m; i++) { read(opr); read(x); read(y); if (opr == 1) { read(z); Add(1, 1, n, x, y, z); } else if (opr == 2) { Sqrt(1, 1, n, x, y); } else { printf("%I64d\n", Query(1, 1, n, x, y)); } } return 0; }