# 【Codeforces 707D】Persistent Bookcase

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,q;

namespace Chair_Tree{
#define CT Chair_Tree
const int MAXN = 2000000;
const int N = 1000+9;
const int Q = 100000+9;

int ls[MAXN],rs[MAXN],sum[MAXN],TY,ans_tmp,cnt,tmp_root,pr[N],pv[N],vout[Q];
int root[Q][N]; bool rev[Q][N];

inline void Clone(int p, int w) {
memcpy(root[w],root[p],sizeof(root[w]));
memcpy(rev[w],rev[p],sizeof(rev[w]));
vout[w] = vout[p];
}

void modify(int p, int &w, int l, int r, int pos){
w = ++cnt; ls[w] = ls[p]; rs[w] = rs[p]; sum[w] = sum[p];
if (l < r) {
int mid = l + r + 1 >> 1;
if (pos < mid) modify(ls[p],ls[w],l,mid-1,pos);
else modify(rs[p],rs[w],mid,r,pos);
sum[w] = sum[ls[w]] + sum[rs[w]];
} else if (sum[w] + TY == 1) sum[w] ^= 1, ans_tmp = 1;
}

inline int modify(int i, int j, int ty, int k){
Clone(k-1,k); ans_tmp = 0; TY = ty^rev[k][i];
modify(root[k][i],tmp_root,1,m,j); root[k][i] = tmp_root;
if (ty == 1) vout[k] += ans_tmp;
else vout[k] -= ans_tmp;
return vout[k];
}

inline int REV(int i,int k){
Clone(k-1,k); rev[k][i] ^= 1;
int tmp = sum[root[k-1][i]], w=tmp;
if (rev[k-1][i]) tmp = m - tmp;
else w = m - w; vout[k] += w - tmp;
return vout[k];
}
};

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}

int main(){
cin>>n>>m>>q;
for (int i=1,ty,x,y;i<=q;i++) {
if (ty == 1) {
printf("%d\n",CT::modify(x,y,1,i));
} else if (ty == 2) {
printf("%d\n",CT::modify(x,y,0,i));
} else if (ty == 3) printf("%d\n",CT::REV(read(),i));
}
return 0;
}


## 13 thoughts to “【Codeforces 707D】Persistent Bookcase”

1. 838627 844807Although you are any with the lucky enough choices, it comes evidently, although capture the fancy of the particular coveted by ly folks other helpful you you meet might possibly nicely have hard times this particular problem. pre owned awnings 315376

2. 296901 637030Spot lets start on this write-up, I seriously believe this amazing website requirements much much more consideration. Ill far more likely once once more to read a terrific deal much more, a lot of thanks that information. 431317

3. 994782 181447i was just browsing along and came upon your internet site. just wantd to say excellent job and this post actually helped me. 557444

4. 145742 464445There exist a couple of a lot of different distinct levels among the California Weight loss program and each and every a person is pretty crucial. Youre procedure stands out as the the actual giving up with all the power. weight loss 552292

5. 159325 794219Totally composed content material material , thankyou for information . 640352

6. 598032 183011I like this internet web site its a master peace ! Glad I detected this on google . 826040

7. 334519 953474I wanted to say Appreciate providing these details, youre performing a terrific job with the site… 849103

8. 475926 278285Good day! This post could not be written any much better! Reading this post reminds me of my previous room mate! He always kept chatting about this. I will forward this write-up to him. Fairly certain he will have a great read. Thanks for sharing! 681113

9. 458604 333646Hi this is somewhat of off topic but I was wondering if blogs use WYSIWYG editors or should you need to manually code with HTML. Im starting a blog soon but have no coding expertise so I wanted to get guidance from someone with experience. Any support would be greatly appreciated! 196520

10. 817940 962975The electronic cigarette uses a battery and a small heating factor the vaporize the e-liquid. This vapor can then be inhaled and exhaled 452711

11. 202550 331049I ran into this page accidentally, surprisingly, this is a great website. The website owner has done an excellent job writing/collecting articles to post, the info here is genuinely insightful. You just secured yourself a guarenteed reader. 154107

12. 719278 675913I discovered your blog web site internet website on the internet and appearance some of your early posts. Continue to keep in the excellent operate. I just now additional increase your Rss to my MSN News Reader. Seeking toward reading far much more from you locating out at a later date! 622083