【简要题意】给一个长度为n序列。进行m次如下操作：

1.add x k:给a[x]加上k。2.ask x y:查询区间[x,y]内所有数的和。3.goto t:回到第t次操作之后的状态。

n,m<=1e5。特别注意：空间限制为8MB

【分析】由于题目背景中出现了可持久化线段树，又有回退到历史版本的操作，所以很多人试图如题目所说的那样卡可持久化的内存。事实证明是卡不过的。
这里有一种神奇的离线算法，大致思路是这样的：

1、去掉3操作就是顺序操作，树状数组无压力。2、树状数组可以支持快速修改和撤回。3、对于回退到t的操作可以认为是从t接出另一条分支。4、而对于每一条分支我们可以用dfs遍历，先存答案再集中输出。

关键词：快速修改和撤回(统计)+回退到历史版本

【code】

#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(){freopen(“memory.in”,”r”,stdin);freopen(“memory.out”,”w”,stdout);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;}