Codeforces 707D Persistent Bookcase(时间树)

forever97 posted @ 2016年8月21日 09:44 in 数据结构-时间树 with tags 时间树 , 728 阅读

 

【题目链接】 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\n",ans[id[i]]);
    return 0;
} 
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter