HDU 5828 Rikka with Sequence（线段树）

题目链接：点击打开链接

思路：

对于该题， 由于存在区间加一个值， 那么所有数都可能永远不会变成1， 但是数与数之间的相对值会趋近于相等。  比如1 2 3 4 5， 进行一次根号操作变成1 1 1 2 2， 而一旦如果相等， 那么他们同时加一个数也是相等的。  所以我们增加一个标记bit[rt]表示该区间内的数是否全部相等，如果相等等于什么。

细节参见代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long LL;
const int maxn = 100010;
LL sum[maxn<<2], add[maxn<<2];
int n, m, vv, bit[maxn<<2];
inline void PushDown(int rt,int m) {
       if (add[rt]) {
              add[rt<<1] += add[rt];
              add[rt<<1|1] += add[rt];
              if(bit[rt<<1]) bit[rt<<1] += add[rt];
              if(bit[rt<<1|1]) bit[rt<<1|1] += add[rt];

              sum[rt<<1] += add[rt] * (m - (m >> 1));
              sum[rt<<1|1] += add[rt] * (m >> 1);
              add[rt] = 0;
       }
}
inline void PushUp(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    if(bit[rt<<1] == bit[rt<<1|1] && bit[rt<<1] && bit[rt<<1|1]) bit[rt] = bit[rt<<1];
    else bit[rt] = 0;
    return ;
}
inline void build(int l, int r, int rt) {
    sum[rt] = 0;
    add[rt] = 0;
    bit[rt] = 0;
    if(l == r) {
        scanf("%d", &vv);
        sum[rt] = vv;
        bit[rt] = vv;
        return ;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
inline void update(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R && bit[rt]) {
        LL res = sqrt(bit[rt] + 0.5);
        add[rt] -= bit[rt] - res;
        sum[rt] = (LL)(r - l + 1) * res;
        bit[rt] = res;
        return ;
    }
    if(l == r) {
        sum[rt] = sqrt(sum[rt] + 0.5);
        return ;
    }
    int m = (l+r)>>1;
    PushDown(rt , r - l + 1);
    if(L <= m) update(L, R, lson);
    if(m < R) update(L, R, rson);
    PushUp(rt);
}
inline void update2(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
            add[rt] += c;
            if(bit[rt]) bit[rt] += c;
            sum[rt] += (LL)c * (r - l + 1);
            return ;
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (L <= m) update2(L , R , c , lson);
       if (m < R) update2(L , R , c , rson);
       PushUp(rt);
}
inline LL query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return sum[rt];
    }
    int m = (l+r)>>1;
    PushDown(rt , r - l + 1);
    LL ans = 0;
    if(L <= m) ans += query(L, R, lson);
    if(m < R) ans += query(L, R, rson);
    return ans;
}
int id[maxn], l[maxn], r[maxn], v[maxn];

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);

        scanf("%d", &m);
        build(1, n, 1);
        int last = -1;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &id[i], &l[i], &r[i]);
            if(l[i] > r[i]) swap(l[i], r[i]);
            if(id[i] == 1) scanf("%d", &v[i]);
            if(id[i] == 3) last = i;
        }
        for(int i = 1; i <= m; i++) {
            if(last < i) break;
            if(id[i] == 1) {
                update2(l[i], r[i], v[i], 1, n, 1);
            }
            else if(id[i] == 2) {
                update(l[i], r[i], 1, n, 1);
            }
            else {
                printf("%I64d\n", query(l[i], r[i], 1, n, 1));
            }
        }
    }
    return 0;
}