题目链接：http://codeforces.com/contest/707/my
看了这位大神的详细分析，一下子明白了。链接：http://blog.csdn.net/queuelovestack/article/details/52269321
搞了两天，终于彻底理解了。本来觉得怎么也不可能和DFS扯上关系，结果以操作的编号建树，对于其他3个操作，直接dfs即可。
在执行操作④之后,书架的状态其实已经回到了之前的某种状态k那么,如果我们从状态k出发,直接去推算出所有经操作④会回到状态k的状态,这样整体就是一个树。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+;
int n,m,k;
struct node
{
int x,y;
};
node q[];
vector<int> g[];
int l[maxn][maxn];
int op[];
int ans[];
void dfs(int u,int sum)
{
ans[u] = sum;
for(int i=;i<g[u].size();i++)
{
int v = g[u][i];
int opp = op[v];
int x = q[v].x;
int y = q[v].y;
if(opp==)
{
if(l[x][y])
{
dfs(v,sum);
}
else
{
l[x][y] = ;
dfs(v,sum+);
l[x][y] = ;
}
}
else if(opp==)
{
if(!l[x][y])
{
dfs(v,sum);
}
else
{
l[x][y] = ;
dfs(v,sum-);
l[x][y] = ;
}
}
else if(opp==)
{
int cur = ;
for(int j=;j<=m;j++)
{
if(l[x][j])
{
l[x][j] = ;
cur--;
}
else
{
l[x][j] = ;
cur++;
}
}
dfs(v,sum+cur);
for(int j=;j<=m;j++)
{
if(l[x][j]) l[x][j] = ;
else l[x][j] = ;
}
}
else
{
dfs(v,sum);
}
}
}
int main()
{
cin>>n>>m>>k;
for(int i=;i<=k;i++)
{
int sel;
scanf("%d",&sel);
op[i] = sel;
if(sel!=)
{
if(sel<=)
{
scanf("%d %d",&q[i].x,&q[i].y);
g[i-].push_back(i);
}
else
{
scanf("%d",&q[i].x);
g[i-].push_back(i);
}
}
else
{
scanf("%d",&q[i].x);
g[q[i].x].push_back(i);
}
}
dfs(,);
for(int i=;i<=k;i++)
{
printf("%d\n",ans[i]);
}
return ;
}