PYOJ 44. 【HNSDFZ2016 #6】可持久化线段树

#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=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f; 
}
const int N=1.5e6+10;
const int s=(1<<20);
struct node{int v,next;}e[N];
struct data{
    int opt,ver,l,r;
}o[N];int cnt=1,tot=0;
int n,m,last[N],head[N],ans[N],t[s<<1];
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>>=1) t[x]+=p;
}
void del(int x,int p){
    for(x+=s;x;x>>=1) t[x]-=p;
}
inline int query(int l,int r){
    int ret=0;
    for(l+=s-1,r+=s+1;l^r^1;l>>=1,r>>=1){
        if(!(l&1)) ret+=t[l^1];
        if(r&1) ret+=t[r^1];
    }
    return ret;
}
void dfs(int x){
    if(o[x].opt==1) updata(o[x].l,o[x].r);
    else if(o[x].opt==2) 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==1) del(o[x].l,o[x].r);
}
int main(){
    n=read();m=read();char s[2];
    last[1]=0;
    for(int i=1;i<=m;i++){
        scanf("%s",s);o[i].ver=read();
        if(s[0]=='C') o[i].opt=0;
        else if(s[0]=='A') o[i].opt=1;
        else o[i].opt=2;
        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!=2) ans[i]=-1;
    }
    dfs(1);
    for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%d
",ans[i]);
    return 0;
}