【题目链接】 http://codeforces.com/problemset/problem/707/D
【题目大意】
给出一个矩阵，要求满足如下操作，单个位置x|=1或者x&=0，一行的数全部取反，回到第k个操作。要求每次操作后输出这个矩阵中数字的和。
【题解】
由于存在操作回溯，考虑使用可持久化数据结构或者建立离线操作树。因为懒，没写持久化。对于每个操作，将它和时间顺序上的上一个节点连边，这样子就形成了一棵树，对这棵树从根节点开始遍历，递归处理，每次处理完一棵子树就回溯操作，这样子就能离线处理操作的持久化了。
【代码】
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1005,M=100005;
int k,q,n,m,t[N],f[N][N],s[N],last=0,ans[M],op[M],x[M],y[M],id[M];
vector<int> v[M];
void dfs(int pre,int w){
int flag=0;
if(op[w]==1){
if(f[x[w]][y[w]]^t[x[w]])ans[w]=ans[pre];
else{
f[x[w]][y[w]]^=1;
if(f[x[w]][y[w]])s[x[w]]++,flag=1;else s[x[w]]--;
ans[w]=ans[pre]+1;
}
}else if(op[w]==2){
if(f[x[w]][y[w]]^t[x[w]]){
f[x[w]][y[w]]^=1;
if(f[x[w]][y[w]])s[x[w]]++,flag=1;else s[x[w]]--;
ans[w]=ans[pre]-1;
}else ans[w]=ans[pre];
}else if(op[w]==3){
if(t[x[w]]==0)ans[w]=ans[pre]-s[x[w]]+m-s[x[w]];
else ans[w]=ans[pre]-(m-s[x[w]])+s[x[w]];
t[x[w]]^=1;
}
for(int i=0;i<v[w].size();i++)dfs(w,v[w][i]);
if(op[w]==1){
if(ans[w]!=ans[pre]){
f[x[w]][y[w]]^=1;
if(flag)s[x[w]]--;else s[x[w]]++;
}
}else if(op[w]==2){
if(ans[w]!=ans[pre]){
f[x[w]][y[w]]^=1;
if(flag)s[x[w]]--;else s[x[w]]++;
}
}else if(op[w]==3){
t[x[w]]^=1;
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=q;i++){
scanf("%d",&op[i]);
if(op[i]==1){
scanf("%d%d",x+i,y+i);
v[last].push_back(id[i]=i);
last=i;
}else if(op[i]==2){
scanf("%d%d",x+i,y+i);
v[last].push_back(id[i]=i);
last=i;
}else if(op[i]==3){
scanf("%d",x+i);
v[last].push_back(id[i]=i);
last=i;
}else{
scanf("%d",&k);
last=id[i]=id[k];
}
}dfs(0,0);
for(int i=1;i<=q;i++)printf("%d
",ans[id[i]]);
return 0;
}