卡内存
hicc0305
2019-02-24 15:30:18
## 题目大意
给出一个长度为n的序列，再给出三种操作：
1.add x k 给a[x]加上k。
2.ask x y 查询区间[x,y]内所有数的和。
3.goto t 回到第t 次操作之后的状态。
## 数据范围
$n,m<=10^5$，$a[i],|k|<=1000$
### 解法
不用什么可持久化线段树
离线记录下所有的操作
建一棵操作树，按照操作树的顺序，用树状数组做就行了。。
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+1000;
struct Edge{int v,nxt;}edge[maxn];
struct node{int id,x,y,ans;}q[maxn];
int head[maxn],tot;
int c[maxn];
int n,m;
char s[20];
inline void read(int &x){
x=0;int fl=1;char tmp=getchar();
while(tmp<'0'||tmp>'9'){if(tmp=='-')fl=-fl;tmp=getchar();}
while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
x=x*fl;
}
inline int lowbit(int x){return x&-x;}
inline void add(int x,int val){while(x<=n)c[x]+=val,x+=lowbit(x);}
inline int ask(int x){int ret=0;while(x>0)ret+=c[x],x-=lowbit(x);return ret;}
void dfs(int u){
if(q[u].id==1) add(q[u].x,q[u].y);
else if(q[u].id==2) q[u].ans=ask(q[u].y)-ask(q[u].x-1);
for(int i=head[u];i!=-1;i=edge[i].nxt)
dfs(edge[i].v);
if(q[u].id==1) add(q[u].x,-q[u].y);
}
int x,y;
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=n;i++) read(x),add(i,x);
for(int i=1;i<=m;i++){
scanf("%s",s);
if(s[1]=='d'){
read(x),read(y);
q[i]=(node){1,x,y,0};
edge[tot]=(Edge){i,head[i-1]},head[i-1]=tot++;
}
else if(s[1]=='s'){
read(x),read(y);
q[i]=(node){2,x,y,0};
edge[tot]=(Edge){i,head[i-1]},head[i-1]=tot++;
}
else{
read(x);
q[i]=(node){3,x,0,0};
edge[tot]=(Edge){i,head[x]},head[x]=tot++;
}
}
dfs(0);
for(int i=1;i<=m;i++)
if(q[i].id==2) printf("%d\n",q[i].ans);
return 0;
}
```