卡内存

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;
}