#44. 【HNSDFZ2016 #6】可持久化线段树
题目描述
现有一序列 AA。您需要写一棵可持久化线段树，以实现如下操作：
-
A v p x：对于版本v的序列，给 ApAp 增加 xx. -
Q v l r：对于版本v的序列，询问 A[l,r]A[l,r] 的区间和。 -
C v：拷贝一份版本v的序列，编号为当前版本总数+1.
版本号从 11 开始；版本 11 的序列，所有元素均为 00.
格式
输入格式
第一行，两个正整数 n,mn,m，表示序列的长度和操作个数。
接下来 mm 行，每行输入一个操作，格式如题目描述所述。
保证任何输入的数都是正整数。
输出格式
对于每一个Q操作，输出一行一个整数，表示对应的区间和。
样例数据
样例输入
5 5
A 1 2 3
Q 1 1 4
C 1
A 2 3 2
Q 2 1 4样例输出
3
5解释
第一次操作后，版本1的序列为：0 3 0 0 0.
第二次操作询问版本1的A[1,4]A[1,4]区间和，答案为0+3+0+0=30+3+0+0=3.
第三次操作将版本1的序列复制到版本2.
第四次操作后，版本2的序列为：0 3 2 0 0.
第五次操作询问版本2的A[1,4]A[1,4]区间和，答案为0+3+2+0=50+3+2+0=5.
数据规模与约定
对于20%20%的数据，有n≤1000,m≤100n≤1000,m≤100.
对于40%40%的数据，有n≤100000,m≤50000n≤100000,m≤50000.
对于100%100%的数据，有n≤1000000,m≤1500000n≤1000000,m≤1500000.
对于100%100%的数据，v,p,l,rv,p,l,r均合法；为了避免爆int，保证1≤x≤101≤x≤10.
时间限制：1s1s
空间限制：128MB
#include<cstdio>
using namespace std;
int read(){
register int x=,f=;
register char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=1.5e6+;
const int s=(<<);
struct node{int v,next;}e[N];
struct data{
int opt,ver,l,r;
}o[N];int cnt=,tot=;
int n,m,last[N],head[N],ans[N],t[s<<];
void add(int x,int y){
e[++tot]=(node){y,head[x]};head[x]=tot;
}
void updata(int x,int p){
for(x+=s;x;x>>=) t[x]+=p;
}
void del(int x,int p){
for(x+=s;x;x>>=) t[x]-=p;
}
inline int query(int l,int r){
int ret=;
for(l+=s-,r+=s+;l^r^;l>>=,r>>=){
if(!(l&)) ret+=t[l^];
if(r&) ret+=t[r^];
}
return ret;
}
void dfs(int x){
if(o[x].opt==) updata(o[x].l,o[x].r);
else if(o[x].opt==) ans[x]=query(o[x].l,o[x].r);
for(int i=head[x];i;i=e[i].next) dfs(e[i].v);
if(o[x].opt==) del(o[x].l,o[x].r);
}
int main(){
n=read();m=read();char s[];
last[]=;
for(int i=;i<=m;i++){
scanf("%s",s);o[i].ver=read();
if(s[]=='C') o[i].opt=;
else if(s[]=='A') o[i].opt=;
else o[i].opt=;
if(o[i].opt){
o[i].l=read();o[i].r=read();
add(last[o[i].ver],i);
last[o[i].ver]=i;
}
else{
add(last[o[i].ver],i);
last[++cnt]=i;
}
if(o[i].opt!=) ans[i]=-;
}
dfs();
for(int i=;i<=m;i++) if(ans[i]!=-) printf("%d\n",ans[i]);
return ;
}