Codeforces 707D Persistent Bookcase(时间树)

发布时间:2017-1-23 4:21:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Codeforces 707D Persistent Bookcase(时间树) ",主要涉及到Codeforces 707D Persistent Bookcase(时间树) 方面的内容,对于Codeforces 707D Persistent Bookcase(时间树) 感兴趣的同学可以参考一下。

【题目链接】 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;

上一篇:CentOS 7.2 安装配置 Percona Server
下一篇:Maven 国内源

相关文章

相关评论