CodeForces - 707D Persistent Bookcase (主席树)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef double db;
 5 const int N=1e6+10,inf=0x3f3f3f3f;
 6 int n,m,Q,sum[N*10],lz[N*10],ch[N*10][2],tot,rt[N];
 7 #define l(u) ch[u][0]
 8 #define r(u) ch[u][1]
 9 #define mid ((l+r)>>1)
10 int cpy(int v) {int u=++tot; l(u)=l(v),r(u)=r(v),sum[u]=sum[v],lz[u]=lz[v]; return u;}
11 void change(int& u,int l,int r) {sum[u]=(r-l+1)-sum[u],lz[u]^=1;}
12 void pd(int& u,int l,int r) {if(lz[u])l(u)=cpy(l(u)),r(u)=cpy(r(u)),change(l(u),l,mid),change(r(u),mid+1,r),lz[u]=0;}
13 void pu(int u) {sum[u]=sum[l(u)]+sum[r(u)];}
14 void rev(int L,int R,int& u,int l=1,int r=n) {
15     u=cpy(u);
16     if(l>=L&&r<=R) {change(u,l,r); return;}
17     if(l>R||r<L)return;
18     pd(u,l,r),rev(L,R,l(u),l,mid),rev(L,R,r(u),mid+1,r),pu(u);
19 }
20 int qry(int p,int& u,int l=1,int r=n) {
21     if(l==r)return sum[u];
22     pd(u,l,r);
23     return p<=mid?qry(p,l(u),l,mid):qry(p,r(u),mid+1,r);
24 }
25 
26 int main() {
27     scanf("%d%d%d",&n,&m,&Q);
28     n*=m;
29     for(int t=1; t<=Q; ++t) {
30         rt[t]=rt[t-1];
31         int f,i,j,k;
32         scanf("%d",&f);
33         if(f==1) {
34             scanf("%d%d",&i,&j);
35             int p=(i-1)*m+j;
36             if(!qry(p,rt[t]))rev(p,p,rt[t]);
37         } else if(f==2) {
38             scanf("%d%d",&i,&j);
39             int p=(i-1)*m+j;
40             if(qry(p,rt[t]))rev(p,p,rt[t]);
41         } else if(f==3) {
42             scanf("%d",&i);
43             int L=(i-1)*m+1,R=(i-1)*m+m;
44             rev(L,R,rt[t]);
45         } else if(f==4) {
46             scanf("%d",&k);
47             rt[t]=rt[k];
48         }
49         printf("%d\n",sum[rt[t]]);
50     }
51     return 0;
52 }