Codeforces Round #368 (Div. 2) D Persistent Bookcase（離線+DFS）

思路：離線把所有操作都存起來，并且對于前三個操作連i-1到i的邊，第四個操作回到第K個結點那麼連k到i的邊，然後DFS記錄變化就可以了，這個過程對于第一次接觸可能不太好了解，可以結合代碼看

注意：加書本的時候如果本來就有的話這個操作相當于無效，同理對于去掉一本書，DFS的時候回溯的時候記得把原來标記的狀态變回原來的

#include<bits/stdc++.h>
using namespace std;
const int maxn =1005;
const int maxq = 1e5+7;
int a[maxn][maxn],ans[maxq],op[maxq];
pair<int,int>op1[maxq];
vector<int>e[maxq];
int sum = 0;
int n,m,q;
void dfs(int x)
{
	if(op[x]!=4)
      ans[x]=sum;
	else
		sum=ans[x];
	int nn,mm;
	for(int i = 0;i<e[x].size();i++)
	{
		int v = e[x][i];
		if(op[v]==1)
		{
			int op1flag=0;
            if(a[op1[v].first][op1[v].second]==0)
			{ 
				a[op1[v].first][op1[v].second]=1;
			    sum++;
				op1flag = 1;
			}
			nn = op1[v].first;
			mm = op1[v].second;
			dfs(v);
	        if(op1flag)
                a[nn][mm]=0,sum--;
		}
		if(op[v]==2)
		{
			int op2flag = 0;
			if(a[op1[v].first][op1[v].second]==1)
			   a[op1[v].first][op1[v].second]=0,sum--,op2flag=1;
			nn=op1[v].first,mm=op1[v].second;
			dfs(v);
		    if(op2flag)
		        a[nn][mm]=1,sum++;
		}
		if(op[v]==3)
		{
			nn = op1[v].first;
			for(int j = 1;j<=m;j++)
			{
				if(a[nn][j])
				{
					a[nn][j]=0;
					sum--;
				}
				else
				{
					a[nn][j]=1;
					sum++;
				}
			}
			dfs(v);
	        for(int j = 1;j<=m;j++)
		    {
			    if(a[nn][j])
			    {
				    a[nn][j]=0;
				    sum++;
			    }
			    else
			    {
				    a[nn][j]=1;
				    sum--;
			    }
		    } 
		}
		if(op[v]==4)
		{
			ans[v]=ans[op1[v].first];
			dfs(v);
		}
	}
}

int main()
{
   scanf("%d%d%d",&n,&m,&q);
   for(int i = 1;i<=q;i++)
   {
	   scanf("%d",&op[i]);
	   if(op[i]==1)
	   {
		   int nn,mm;
		   scanf("%d%d",&nn,&mm);
		   op1[i]=make_pair(nn,mm);
           e[i-1].push_back(i);
	   }
	   if(op[i]==2)
	   {
		   int nn,mm;
		   scanf("%d%d",&nn,&mm);
		   op1[i]=make_pair(nn,mm);
		   e[i-1].push_back(i);
	   }
	   if(op[i]==3)
	   {
		   int nn;
		   scanf("%d",&nn);
		   op1[i]=make_pair(nn,-1);
		   e[i-1].push_back(i);
	   }
	   if(op[i]==4)
	   {
		   int k;
		   scanf("%d",&k);
		   e[k].push_back(i);
		   op1[i] = make_pair(k,-1);
	   }
   }

   dfs(0);

   for(int i = 1;i<=q;i++)
	   printf("%d\n",ans[i]);
}