首页 > 代码库 > 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双面棋盘