2017-team2-dynamicbridge

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
typedef pair<int,int> P;
const int N=100010,M=100010,K=19;
int n,m,i,ans[M];
bool use[M],ex[M],cut[M],vis[N];
int g[N],v[M<<1],w[M<<1],nxt[M<<1],ed,f[N],dfn[N],low[N],num,from[N];
int G[N],V[M<<1],W[N<<1],NXT[N<<1],ED,id[N],sum[N],vip[N];
int O,ce,all,pos[M],q[K][M];
map<P,int> T;
struct E{
    int x,y,w;
    E(){}
    E(int _x,int _y,int _w){ x=_x,y=_y,w=_w;}
}e[K][M];
inline int ask(int x,int y){
    if (x==y)return 0;
    if (x>y)swap(x,y);
    int&t=T[P(x,y)];
    if(!t)e[0][t=++ce]=E(x,y,0);
    return t;
}
inline void add(int x,int y,int z){ v[++ed]=y; w[ed]=z;nxt[ed]=g[x]; g[x]=ed; }
inline void ADD(int x,int y,int z){ V[++ED]=y; W[ED]=z;NXT[ED]=G[x]; G[x]=ED; }
void tarjan(int x){
    dfn[x]=low[x]=++num;
    for(int i=g[x];i;i=nxt[i])if (!dfn[v[i]]){
        f[v[i]]=w[i],tarjan(v[i]);
        if (low[x]>low[v[i]])low[x]=low[v[i]];
    }else if (f[x]!=w[i]&&low[x]>dfn[v[i]])low[x]=dfn[v[i]];
    if (f[x]&&low[x]==dfn[x])cut[f[x]]=1;
}
void dfs(int x,int y){
    from[x]=y;
    for(int i=g[x];i;i=nxt[i])if(!from[v[i]]&&!cut[w[i]])dfs(v[i],y);
}
inline void newedge(int x,int y,int w){all-=w; e[O][++ce]=E(x,y,w); }
void compress(int x,int y)  
{   
    int d=0;    
    vis[x]=1;
    for(int i=G[x];i;i=NXT[i]){
        int u=V[i];
        if (u==y)continue;
        sum[u]=sum[x]+W[i];
        compress(u,x);
        if (!id[u])continue;
        d++;
        id[x]^=id[u];
    }
    if (d>1)vip[x]=1;
    if (vip[x]){
        for(int i=G[x];i;i=NXT[i]){
            int u=V[i];
            if (u==y)continue;
            int t=id[u];
            if (t)newedge(x,t,sum[t]-sum[x]);
        }
        id[x]=x;
    }
}

void solve(int o,int l,int r,int n,int m,int pre){
    O=o+1;
    int i;
    if (l==r){
        for(i=1;i<=m;i++)cut[i]=0;
        for(ed=0,i=1;i<=n;i++)g[i]=f[i]=dfn[i]=low[i]=from[i]=0;
        num=0;
        e[o][q[o][l]].w^=1;
        for(i=1;i<=m;i++)if(e[o][i].w){
            int x=e[o][i].x,y=e[o][i].y;
            add(x,y,i); add(y,x,i);
        }
        for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
        for(i=1;i<=m;i++)if(cut[i])pre+=e[o][i].w;
        e[o][q[o][l]].w^=1;
        ans[l]=pre;
        return;
    }
    for(i=1;i<=m;i++)use[i]=cut[i]=pos[i]=0;
    for(ed=0,i=1;i<=n;i++)g[i]=f[i]=dfn[i]=low[i]=from[i]=0;
    num=0;
    int cnt=0;
    for(i=l;i<=r;i++)use[q[o][i]]=1;
    for(i=1;i<=m;i++)if(!use[i]&&e[o][i].w){
        int x=e[o][i].x,y=e[o][i].y;
        add(x,y,i); add(y,x,i);
    }
    for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(i=1;i<=n;i++)if(!from[i])dfs(i,++cnt);
    for(ED=0,i=1;i<=cnt;i++)vis[i]=vip[i]=G[i]=id[i]=sum[i]=0;
    ce=all=0;
    for(i=1;i<=m;i++)if(!use[i]&&e[o][i].w){
        int x=e[o][i].x,y=e[o][i].y;
        x=from[x],y=from[y];
        if (x==y)continue;
        ADD(x,y,e[o][i].w); ADD(y,x,e[o][i].w);
        all+=e[o][i].w;
    }
    for(i=l;i<=r;i++){
        int t=q[o][i];
        if (!t)continue;
        vip[from[e[o][t].x]]=vip[from[e[o][t].y]]=1;
    }
    for(i=1;i<=cnt;i++)if(vip[i]&&!vis[i])compress(i,0);
    int mid=(l+r)>>1,_ce=ce,cv=0;
    for(i=1;i<=cnt;i++)if(vip[i])vip[i]=++cv;
    pre+=all;
    for(i=1;i<=ce;i++)e[o+1][i].x=vip[e[o+1][i].x],e[o+1][i].y=vip[e[o+1][i].y];
    for(i=1;i<=m;i++)if(use[i]){
        int x=e[o][i].x,y=e[o][i].y;
        e[o+1][++ce]=E(vip[from[x]],vip[from[y]],e[o][i].w);
        pos[i]=ce;
    }
    for(i=l;i<=r;i++)q[o+1][i]=pos[q[o][i]];
    solve(o+1,l,mid,cv,ce,pre);
    ce=_ce;
    for(i=1;i<=m;i++)use[i]=0;
    for(i=l;i<=r;i++)use[q[o][i]]=1;
    for(i=1;i<=m;i++)if(use[i])ex[i]=e[o][i].w;
    for(i=l;i<=mid;i++)ex[q[o][i]]^=1;
    for(i=1;i<=m;i++)if(use[i])e[o+1][++ce].w=ex[i];
    solve(o+1,mid+1,r,cv,ce,pre);
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        char s[9];
        int x,y;
        scanf("%s%d%d",s,&x,&y);
        q[0][i]=ask(x,y);
    }
    solve(0,1,m,n,ce,0);
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
}}}

typedef pair<int,int> P;
const int N=100010,M=100010,K=19;
int n,m,i,ans[M];
bool use[M],ex[M],cut[M],vis[N];
int g[N],v[M<<1],w[M<<1],nxt[M<<1],ed,f[N],dfn[N],low[N],num,from[N];
int G[N],V[M<<1],W[N<<1],NXT[N<<1],ED,id[N],sum[N],vip[N];
int O,ce,all,pos[M],q[K][M];
map<P,int> T;
struct E{
    int x,y,w;
    E(){}
    E(int _x,int _y,int _w){ x=_x,y=_y,w=_w;}
}e[K][M];
inline int ask(int x,int y){
    if (x==y)return 0;
    if (x>y)swap(x,y);
    int&t=T[P(x,y)];
    if(!t)e[0][t=++ce]=E(x,y,0);
    return t;
}
inline void add(int x,int y,int z){ v[++ed]=y; w[ed]=z;nxt[ed]=g[x]; g[x]=ed; }
inline void ADD(int x,int y,int z){ V[++ED]=y; W[ED]=z;NXT[ED]=G[x]; G[x]=ED; }
void tarjan(int x){
    dfn[x]=low[x]=++num;
    for(int i=g[x];i;i=nxt[i])if (!dfn[v[i]]){
        f[v[i]]=w[i],tarjan(v[i]);
        if (low[x]>low[v[i]])low[x]=low[v[i]];
    }else if (f[x]!=w[i]&&low[x]>dfn[v[i]])low[x]=dfn[v[i]];
    if (f[x]&&low[x]==dfn[x])cut[f[x]]=1;
}
void dfs(int x,int y){
    from[x]=y;
    for(int i=g[x];i;i=nxt[i])if(!from[v[i]]&&!cut[w[i]])dfs(v[i],y);
}
inline void newedge(int x,int y,int w){all-=w; e[O][++ce]=E(x,y,w); }
void compress(int x,int y)  
{   
    int d=0;    
    vis[x]=1;
    for(int i=G[x];i;i=NXT[i]){
        int u=V[i];
        if (u==y)continue;
        sum[u]=sum[x]+W[i];
        compress(u,x);
        if (!id[u])continue;
        d++;
        id[x]^=id[u];
    }
    if (d>1)vip[x]=1;
    if (vip[x]){
        for(int i=G[x];i;i=NXT[i]){
            int u=V[i];
            if (u==y)continue;
            int t=id[u];
            if (t)newedge(x,t,sum[t]-sum[x]);
        }
        id[x]=x;
    }
}
void solve(int o,int l,int r,int n,int m,int pre){
    O=o+1;
    int i;
    if (l==r){
        for(i=1;i<=m;i++)cut[i]=0;
        for(ed=0,i=1;i<=n;i++)g[i]=f[i]=dfn[i]=low[i]=from[i]=0;
        num=0;
        e[o][q[o][l]].w^=1;
        for(i=1;i<=m;i++)if(e[o][i].w){
            int x=e[o][i].x,y=e[o][i].y;
            add(x,y,i); add(y,x,i);
        }
        for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
        for(i=1;i<=m;i++)if(cut[i])pre+=e[o][i].w;
        e[o][q[o][l]].w^=1;
        ans[l]=pre;
        return;
    }
    for(i=1;i<=m;i++)use[i]=cut[i]=pos[i]=0;
    for(ed=0,i=1;i<=n;i++)g[i]=f[i]=dfn[i]=low[i]=from[i]=0;
    num=0;
    int cnt=0;
    for(i=l;i<=r;i++)use[q[o][i]]=1;
    for(i=1;i<=m;i++)if(!use[i]&&e[o][i].w){
        int x=e[o][i].x,y=e[o][i].y;
        add(x,y,i); add(y,x,i);
    }
    for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(i=1;i<=n;i++)if(!from[i])dfs(i,++cnt);
    for(ED=0,i=1;i<=cnt;i++)vis[i]=vip[i]=G[i]=id[i]=sum[i]=0;
    ce=all=0;
    for(i=1;i<=m;i++)if(!use[i]&&e[o][i].w){
        int x=e[o][i].x,y=e[o][i].y;
        x=from[x],y=from[y];
        if (x==y)continue;
        ADD(x,y,e[o][i].w); ADD(y,x,e[o][i].w);
        all+=e[o][i].w;
    }
    for(i=l;i<=r;i++){
        int t=q[o][i];
        if (!t)continue;
        vip[from[e[o][t].x]]=vip[from[e[o][t].y]]=1;
    }
    for(i=1;i<=cnt;i++)if(vip[i]&&!vis[i])compress(i,0);
    int mid=(l+r)>>1,_ce=ce,cv=0;
    for(i=1;i<=cnt;i++)if(vip[i])vip[i]=++cv;
    pre+=all;
    for(i=1;i<=ce;i++)e[o+1][i].x=vip[e[o+1][i].x],e[o+1][i].y=vip[e[o+1][i].y];
    for(i=1;i<=m;i++)if(use[i]){
        int x=e[o][i].x,y=e[o][i].y;
        e[o+1][++ce]=E(vip[from[x]],vip[from[y]],e[o][i].w);
        pos[i]=ce;
    }
    for(i=l;i<=r;i++)q[o+1][i]=pos[q[o][i]];
    solve(o+1,l,mid,cv,ce,pre);
    ce=_ce;
    for(i=1;i<=m;i++)use[i]=0;
    for(i=l;i<=r;i++)use[q[o][i]]=1;
    for(i=1;i<=m;i++)if(use[i])ex[i]=e[o][i].w;
    for(i=l;i<=mid;i++)ex[q[o][i]]^=1;
    for(i=1;i<=m;i++)if(use[i])e[o+1][++ce].w=ex[i];
    solve(o+1,mid+1,r,cv,ce,pre);
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        char s[9];
        int x,y;
        scanf("%s%d%d",s,&x,&y);
        q[0][i]=ask(x,y);
    }
    solve(0,1,m,n,ce,0);
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}