「SPOJ TTM 」To the moon「标记永久化」

向右看齐 2023-08-17 17:31 27阅读 0赞

**题意**

概括为主席树区间加区间询问

**题解**

记录一下标记永久化的方法。每个点存`add`和`sum`两个标记，表示这个区间整个加多少，区间和是多少（这个区间和不包括祖先结点区间加）

然后区间加的时候，给路上每结点的`sum`更新，然后到达完整区间后更新`add`。询问的时候把路径上所有结点（不包括自己）的`add`加起来乘以区间长度，再加上`sum`

大概思想就是：区间内的加法用`sum`维护，区间外的加法询问的时候再考虑贡献

#include <algorithm>
    #include <cstdio>
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1e5 + 10;
    
    int n, m, a[N];
    int T[N], id, L[N << 6], R[N << 6];
    ll s[N << 6], add[N << 6];
    
    void build(int &rt, int l, int r) {
    	rt = ++ id;
    	if(l < r) {
    		int mid = (l + r) >> 1;
    		build(L[rt], l, mid);
    		build(R[rt], mid + 1, r);
    		s[rt] = s[L[rt]] + s[R[rt]];
    	} else s[rt] = a[l];
    }
    
    void update(int &rt, int pre, int l, int r, int ql, int qr, int x) {
    	rt = ++ id; L[rt] = L[pre]; R[rt] = R[pre];
    	s[rt] = s[pre] + (qr - ql + 1) * x; add[rt] = add[pre];
    	if(ql == l && r == qr) { add[rt] += x; return ; }
    	int mid = (l + r) >> 1;
    	if(qr <= mid) update(L[rt], L[pre], l, mid, ql, qr, x);
    	else if(ql > mid) update(R[rt], R[pre], mid + 1, r, ql, qr, x);
    	else {
    		update(L[rt], L[pre], l, mid, ql, mid, x);
    		update(R[rt], R[pre], mid + 1, r, mid + 1, qr, x);
    	}
    }
    
    ll query(int rt, int l, int r, int ql, int qr, ll sum = 0) {
    	if(ql == l && qr == r) return sum * (r - l + 1) + s[rt];
    	sum += add[rt];
    	int mid = (l + r) >> 1;
    	if(qr <= mid) return query(L[rt], l, mid, ql, qr, sum);
    	if(ql > mid) return query(R[rt], mid + 1, r, ql, qr, sum);
    	return query(L[rt], l, mid, ql, mid, sum) + query(R[rt], mid + 1, r, mid + 1, qr, sum);
    }
    
    int main() {
    	scanf("%d%d", &n, &m);
    	for(int i = 1; i <= n; i ++)
    		scanf("%d", a + i);
    	static char op[5];
    	int tnow = 0; build(T[0], 1, n);
    	for(int l, r, d, i = 1; i <= m; i ++) {
    		scanf("%s", op);
    		if(* op == 'C') {
    			scanf("%d%d%d", &l, &r, &d);
    			update(T[tnow + 1], T[tnow], 1, n, l, r, d);
    			tnow ++;
    		}
    		if(* op == 'Q') {
    			scanf("%d%d", &l, &r);
    			printf("%lld\n", query(T[tnow], 1, n, l, r));
    		}
    		if(* op == 'H') {
    			scanf("%d%d%d", &l, &r, &d);
    			printf("%lld\n", query(T[d], 1, n, l, r));
    		}
    		if(* op == 'B') {
    			scanf("%d", &tnow);
    		}
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11307145.html