首页 > 代码库 > bzoj1453: [Wc]Dface双面棋盘
bzoj1453: [Wc]Dface双面棋盘
Description
Input
Output
经典的按时间分治维护图的动态连通性
#include<cstdio>#include<vector>int n,m,ans[2];int v[207][207],id[207][207],idp=0,t1[207][207],t2[207][207];int f[40007],h[40007],aa[40007][2];int*op1[1000007],op2[1000007],opp=0;inline void set(int*a,int b){ op1[opp]=a; op2[opp++]=*a; *a=b;}struct op{ op*nx; int x,y,c; void run(){ while(x!=f[x])x=f[x]; while(y!=f[y])y=f[y]; if(x==y)return; set(ans+c,ans[c]-1); if(h[x]<h[y])set(f+x,y); else{ if(h[x]==h[y])set(h+x,h[x]+1); set(f+y,x); } }}os[3000007],*p=os,o1;int l1,r1,a1,b1,c1;struct node{ node*lc,*rc; int L,R; op*o; void ins(){ if(l1<=L&&R<=r1){ *p=(op){o,a1,b1,c1}; o=p++; return; } int M=L+R>>1; if(l1<=M)lc->ins(); if(r1>M)rc->ins(); } void dfs(){ int tk=opp; for(;o;o=o->nx)o->run(); if(L==R){ aa[L][0]+=aa[L-1][0]; aa[L][1]+=aa[L-1][1]; printf("%d %d\n",ans[1]+aa[L][1],ans[0]+aa[L][0]); }else{ lc->dfs(); rc->dfs(); } while(opp!=tk){ --opp; *op1[opp]=op2[opp]; } }}ns[20007],*np=ns,*rt;node*build(int L,int R){ node*w=np++; w->L=L;w->R=R; if(L!=R){ int M=L+R>>1; w->lc=build(L,M); w->rc=build(M+1,R); } return w;}void ins(int&l,int r,int a,int b,int c){ l1=l;r1=r;a1=a;b1=b;c1=c; if(l1<=r1)rt->ins(); l=0;}int main(){ scanf("%d",&n,&m); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ scanf("%d",v[i]+j); ++ans[v[i][j]]; id[i][j]=++idp; f[idp]=idp; } } for(int i=1;i<n;++i){ for(int j=1;j<=n;++j)if(v[i][j]==v[i+1][j])t1[i][j]=1; } for(int i=1;i<=n;++i){ for(int j=1;j<n;++j)if(v[i][j]==v[i][j+1])t2[i][j]=1; } scanf("%d",&m); rt=build(1,m); for(int i=1,x,y;i<=m;++i){ scanf("%d%d",&x,&y); if(x>1){ if(v[x][y]!=v[x-1][y])t1[x-1][y]=i; else ins(t1[x-1][y],i-1,id[x][y],id[x-1][y],v[x][y]); } if(x<n){ if(v[x][y]!=v[x+1][y])t1[x][y]=i; else ins(t1[x][y],i-1,id[x][y],id[x+1][y],v[x][y]); } if(y>1){ if(v[x][y]!=v[x][y-1])t2[x][y-1]=i; else ins(t2[x][y-1],i-1,id[x][y],id[x][y-1],v[x][y]); } if(y<n){ if(v[x][y]!=v[x][y+1])t2[x][y]=i; else ins(t2[x][y],i-1,id[x][y],id[x][y+1],v[x][y]); } aa[i][v[x][y]]=-1; v[x][y]^=1; aa[i][v[x][y]]=1; } for(int i=1;i<n;++i){ for(int j=1;j<=n;++j)if(v[i][j]==v[i+1][j])ins(t1[i][j],m,id[i][j],id[i+1][j],v[i][j]); } for(int i=1;i<=n;++i){ for(int j=1;j<n;++j)if(v[i][j]==v[i][j+1])ins(t2[i][j],m,id[i][j],id[i][j+1],v[i][j]); } rt->dfs(); return 0;}
bzoj1453: [Wc]Dface双面棋盘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。