题目大意：有三种操作，第一种操作，在i 个书架，j个位置放一本书，第二种操作，取下第i个书架，j 个位置的书，第三种操作，
把第i个书架所有没有书的位置放上书，有书的位置拿掉数，第四种操作，回到第k个操作，问你每次操作后书的总数。
两种方法：1、离线之后，建树，对于op不等于4的操作i，建一条i-1 到 i的边，对于op==4的造作i，建一条k 到 i的边，书上跑一遍dfs
得出答案，回溯的时候恢复状态。
2、无脑主席树，需要注意的是要用bitset优化一下空间，不然会爆炸。。。。
离线
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mk make_pair #define pii pair<int,int> #define read(x) scanf("%d",&x) #define lread(x) scanf("%lld",&x) using namespace std; typedef long long ll; const int N=2e3+7; const int M=1e5+7; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; struct node { int op,r,c; }qus[M<<1]; int n,m,q,all,ans[M],sum[N],cnt[N][N],pos[M]; bool flag[N]; vector<int> e[M]; void change(int x) { int op=qus[x].op; int r=qus[x].r,c=qus[x].c; if(op==1) { if(flag[r] && cnt[r][c]==1) all++,sum[r]++,cnt[r][c]=0; else if(!flag[r] && !cnt[r][c]) all++,sum[r]++,cnt[r][c]=1; } else if(op==2) { if(flag[r] && !cnt[r][c]) all--,sum[r]--,cnt[r][c]=1; else if(!flag[r] && cnt[r][c]==1) all--,sum[r]--,cnt[r][c]=0; } else if(op==3) { int pre=sum[r]; sum[r]=m-sum[r]; all+=sum[r]-pre; flag[r]=!flag[r]; } } void dfs(int u) { bool flag=true; int p=all; if(u!=0) change(u); if((qus[u].op==1 || qus[u].op==2) && all==p) flag=false; ans[u]=all; for(int v:e[u]) dfs(v); if(u!=0 && flag) change(u+q); } int main() { memset(pos,-1,sizeof(pos)); read(n); read(m); read(q); for(int i=1;i<=q;i++) { int op,r,c=0; read(op); read(r); if(op-3<0) read(c); qus[i]={op,r,c}; if(op==1) qus[i+q]={2,r,c}; else if(op==2) qus[i+q]={1,r,c}; else if(op==3) qus[i+q]={3,r,c}; else qus[i+q]={4,r,c}; if(qus[i].op!=4) e[i-1].push_back(i); else e[r].push_back(i); } dfs(0); for(int i=1;i<=q;i++) printf("%d ",ans[i]); return 0; } /* */
在线主席树
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mk make_pair #define pii pair<int,int> #define read(x) scanf("%d",&x) #define lread(x) scanf("%lld",&x) using namespace std; typedef long long ll; const int N=1e3+1; const int M=1e5+1; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; int n,m,q; struct seg_tree { int tot,root[M]; struct node { bitset<1005> b; bool filp; int sum,l,r; }a[M*20]; void up(int x,int l,int r){ a[x].sum=a[l].sum+a[r].sum; } void updata(int l,int r,int &x,int y,int pos,int num,int op) { a[++tot]=a[y]; x=tot; if(l==r) { if(op==1) { if(!a[x].filp && !a[x].b[num]) a[x].b[num]=true,a[x].sum++; else if(a[x].filp && a[x].b[num]) a[x].b[num]=false,a[x].sum++; } else if(op==2) { if(!a[x].filp && a[x].b[num]) a[x].b[num]=false,a[x].sum--; else if(a[x].filp && !a[x].b[num]) a[x].b[num]=true,a[x].sum--; } else if(op==3) { a[x].sum=m-a[x].sum; a[x].filp=!a[x].filp; } return; } int mid=(l+r)>>1; if(pos<=mid) updata(l,mid,a[x].l,a[y].l,pos,num,op); else updata(mid+1,r,a[x].r,a[y].r,pos,num,op); up(x,a[x].l,a[x].r); } }seg; int main() { read(n); read(m); read(q); for(int i=1;i<=q;i++) { int op,r,c=0; read(op); read(r); if(op<=2) read(c); if(op!=4) seg.updata(1,n,seg.root[i],seg.root[i-1],r,c,op); else seg.updata(1,n,seg.root[i],seg.root[r],r,c,op); printf("%d ",seg.a[seg.root[i]].sum); } return 0; } /* */