Codeforces Round #368 (Div. 2)（D. Persistent Bookcase 离线转化DAG）

本文主要是介绍Codeforces Round #368 (Div. 2)（D. Persistent Bookcase 离线转化DAG），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

给出n*m的书架，4种操作
1，x,y，如果(x,y)空，该位置则放一本书
2，x,y，如果(x,y)不空，该位置拿走一本书
3，x, 把这一层有书的拿出，没书的放上书，即反转
4，x, 返回到第x操作后的书架的状态

初始书架是空的，要注意一点的是，题目可能在没书的地方拿书，有书的地方放书，明显这样的操作是不成功的，没影响的，所以要标记一下。

麻烦的是第4操作，无法记录每次操作的状态，直接暴力也会超时，可以这样考虑：
第k步操作的结果，一般是由第k-1步操作的结果加上第k步的操作转化而来，但是当第k步是操作4的时候，那么第k步就还可以从第x步操作转化而来，所以我们以此建立DAG，进行dfs，回溯的时候取消操作，在继续遍历其他的儿子。巧妙！

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 1e5+10;
const int inf  = 1 << 28;int n,m,q;struct node{int type,x,y,ok,ans;
}Q[maxn];vector<int> G[maxn];
bitset<1005> bit[1005],all;
int total;void todo(int i){if(Q[i].type==1){total -= bit[Q[i].x].count();if(!bit[Q[i].x][Q[i].y])Q[i].ok=true,bit[Q[i].x][Q[i].y]=1;total += bit[Q[i].x].count();}if(Q[i].type==2){total -= bit[Q[i].x].count();if(bit[Q[i].x][Q[i].y]) Q[i].ok=true,bit[Q[i].x][Q[i].y]=0;total += bit[Q[i].x].count();}if(Q[i].type==3){total -= bit[Q[i].x].count();bit[Q[i].x]^=all;total += bit[Q[i].x].count();}
}void undo(int i){if(Q[i].type==1){total -= bit[Q[i].x].count();if(Q[i].ok)bit[Q[i].x][Q[i].y] = 0;total += bit[Q[i].x].count();}if(Q[i].type==2){total -= bit[Q[i].x].count();if(Q[i].ok)bit[Q[i].x][Q[i].y] = 1;total += bit[Q[i].x].count();}if(Q[i].type==3){total -= bit[Q[i].x].count();bit[Q[i].x]^=all;total += bit[Q[i].x].count();}
}void dfs(int x){todo(x);Q[x].ans = total;for(int i=0;i<G[x].size();i++)dfs(G[x][i]);undo(x);
}int main(){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=q;i++){scanf("%d%d",&Q[i].type,&Q[i].x);if(Q[i].type<=2)scanf("%d",&Q[i].y);if(Q[i].type==4){G[Q[i].x].pb(i);}else {G[i-1].pb(i);}}for(int i=1;i<=m;i++)all[i]=1;dfs(0);for(int i=1;i<=q;i++){printf("%d\n",Q[i].ans);}return 0;
}