题目链接：http://codeforces.com/contest/707/problem/D
题目大意：
(Alina)有一个(n)层，每层有(m)个格子的书架。书架一开始是空的。现在她要在书架上做(q)个操作，操作有四种：
(1) (i) (j)——如果第(i)层的第(j)个格子没有书，那么放一本书进去；
(2) (i) (j)——如果第(i)层的第(j)个格子有书，那么把书拿出来；
(3) (i)——将第(i)层有书的格子都清空，没书的格子都放上书；
(4) (k)——将书架还原到第(k)次操作完成后的状态，如果(k=0)，那么就将书架清空。
每次操作之后，输出现在书架上有多少本书。
知识点： DFS
解题思路：
难点在于第(4)种操作，我们采用离线操作来解决这个困难：先将输入离线保存，然后在此基础上建立(DFS)的状态转移图。我们举第(q)次操作为例，如果操作(q+1)不是第(4)种操作，则建边(q ightarrow (q+1))；如果第(q)次操作是 ("4) (k")，则建边(k ightarrow q). 在这个状态转移图上进行(DFS).
而对于第(3)种操作，只需要用一个标记(flag)来记录即可。
状态用一个(n imes m)的邻接矩阵来记录。
AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e3+10,maxq=1e5+5; 5 bool book[maxn][maxn],flag[maxn]; 6 int ans[maxq]; 7 struct Input{ 8 int ord,i,j; 9 }inp[maxq]; 10 int n,m,q; 11 vector<int> G[maxq]; 12 13 void dfs(int rt,int nans){ 14 bool change=false; 15 //************************************************* 16 //操作 17 if(inp[rt].ord==1){ 18 if(!flag[inp[rt].i]){ 19 if(!book[inp[rt].i][inp[rt].j]){ 20 change=true; 21 book[inp[rt].i][inp[rt].j]=true; 22 nans++; 23 } 24 } 25 else{ 26 if(book[inp[rt].i][inp[rt].j]){ 27 change=true; 28 book[inp[rt].i][inp[rt].j]=false; 29 nans++; 30 } 31 } 32 } 33 else if(inp[rt].ord==2){ 34 if(!flag[inp[rt].i]){ 35 if(book[inp[rt].i][inp[rt].j]){ 36 change=true; 37 book[inp[rt].i][inp[rt].j]=false; 38 nans--; 39 } 40 } 41 else{ 42 if(!book[inp[rt].i][inp[rt].j]){ 43 change=true; 44 book[inp[rt].i][inp[rt].j]=true; 45 nans--; 46 } 47 } 48 } 49 else if(inp[rt].ord==3){ 50 change=true; 51 flag[inp[rt].i]=!flag[inp[rt].i]; 52 int have=0; 53 for(int k=1;k<=m;k++){ 54 if(book[inp[rt].i][k]) have++; 55 } 56 if(flag[inp[rt].i]) nans=nans-have+(m-have); 57 else nans=nans-(m-have)+have; 58 } 59 //******************************************************* 60 ans[rt]=nans; 61 for(int i=0;i<G[rt].size();i++) 62 dfs(G[rt][i],nans); 63 //******************************************************* 64 //还原 65 if(change){ 66 if(inp[rt].ord==1){ 67 if(!flag[inp[rt].i]) 68 book[inp[rt].i][inp[rt].j]=false; 69 else 70 book[inp[rt].i][inp[rt].j]=true; 71 } 72 else if(inp[rt].ord==2){ 73 if(!flag[inp[rt].i]) 74 book[inp[rt].i][inp[rt].j]=true; 75 else 76 book[inp[rt].i][inp[rt].j]=false; 77 } 78 else if(inp[rt].ord==3) 79 flag[inp[rt].i]=!flag[inp[rt].i]; 80 } 81 //*********************************************** 82 } 83 int main(){ 84 scanf("%d%d%d",&n,&m,&q); 85 inp[0].ord=4; 86 for(int k=1;k<=q;k++){ 87 scanf("%d",&inp[k].ord); 88 if(inp[k].ord==1||inp[k].ord==2) scanf("%d%d",&inp[k].i,&inp[k].j); 89 else scanf("%d",&inp[k].i); 90 } 91 for(int k=0;k<=q;k++){ 92 if(inp[k].ord==4&&k!=0) 93 G[inp[k].i].push_back(k); 94 if(inp[k+1].ord!=4&&k+1<=q) 95 G[k].push_back(k+1); 96 } 97 dfs(0,0); 98 for(int i=1;i<=q;i++) 99 printf("%d ",ans[i]); 100 101 return 0; 102 }