[SP11460]TTM - To the moon

摘要

题意：可持久化区间修改查询。.

标记永久化

在主席树上做区间查询，标记持久化。主席树直接维护序列区间和。做修改的时侯，我们对 log 个区间的结点打标记，但是不下传。查询的时侯，遇到路径上标记就累加对应标记的信息。相当于我们做了标记就不再去动这个标记，所以叫作标记永久化。这不是本文的重点。

差分法

考虑普通的区间修改查询。用树状数组的差分方法

于是我们维护两个主席树，主席树维护区间和，一个维护 ，一个维护 . 查询的时侯查询前缀和即可。另外，同一对指针数组可以维护多个主席树（因为主席树只与上个版本有关）

码短。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m;

const int SZ=1<<24;
int tot;
int lc[SZ],rc[SZ],sum[SZ];
int r1[N+M],r2[N+M];

int modify(int pos,int v,int u,int l=1,int r=n){int u2=++tot,mid=(l+r)>>1;
    sum[u2]=sum[u]+v, lc[u2]=lc[u],rc[u2]=rc[u];
    if(l==r)return u2;
    if(pos<=mid)lc[u2]=modify(pos,v,lc[u],l,mid);
    else rc[u2]=modify(pos,v,rc[u],mid+1,r);
    return u2;
}
int query(int pos,int u,int l=1,int r=n){//pos 的前缀和
    if(r<=pos||l==r)return sum[u];
    int mid=(l+r)>>1;
    if(pos<=mid)return query(pos,lc[u],l,mid);
    else return sum[lc[u]]+query(pos,rc[u],mid+1,r);
}

int a[N];
int pre(int pos,int u1,int u2){
    return a[pos]+(pos+1)*query(pos,u1)-query(pos,u2);
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]), a[i]+=a[i-1];
    char op[5];
    int l,r,d,t=0;//t 是当前时间戳
    for(int i=1;i<=m;i++){scanf("%s",op);
        if(op[0]=='C'){scanf("%lld%lld%lld",&l,&r,&d);
            ++t;// 更新时间戳
            r1[t]=modify(r+1,-d, modify(l,d,r1[t-1]));
            r2[t]=modify(r+1,-d*(r+1), modify(l,d*l,r2[t-1]));
        }else if(op[0]=='Q'){scanf("%lld%lld",&l,&r);
            printf("%lld\n",pre(r,r1[t],r2[t])-pre(l-1,r1[t],r2[t]));
        }else if(op[0]=='H'){scanf("%lld%lld%lld",&l,&r,&d);
            printf("%lld\n",pre(r,r1[d],r2[d])-pre(l-1,r1[d],r2[d]));
        }else scanf("%lld",&t);
    }
    return 0;
}