【Codeforces 576E】Painting Edges | Mrsrz's blog

线段树分治

题目大意：

给定一张无向图和 $k$ 种颜色，每条边开始时没有颜色，后来会涂上颜色。

需要保证，任意时刻，对任意一种颜色，只保留该种颜色的边，原图是一张二分图。

有 $q$ 次操作，每次会将一条边染成一种颜色，如果染色后合法则染，否则不染。

需要对每次染色操作输出是否染色成功。

题解：

线段树分治。

由于本题每条边的出现时间不确定，因此我们一边进行分治一边插入边。

具体地，用 $k$ 个可撤销并查集维护每种颜色的边的信息。需要支持查询两点之间距离的奇偶性。

递归的时候，先向时间早的结点递归，到了叶子结点，判断这条边是否能加入。如果可以，那么这条边在下一个时刻开始的一段区间内存在；如果不可以，那么这条边原本应该存在的时间，都仍然是原来的颜色。把新的边加入分治结构中即可。

由于保证插入的边所对应的时间范围一定在当前时间之后，因此不会出现冲突。

关于如何用并查集维护两点之间距离的奇偶性。我们对并查集上每个结点，记录 $d_i$ 表示 $i$ 到其并查集上父亲的原图上距离的奇偶性。如果两个点本身不在同一个并查集中那显然没问题。如果在的话，连上这条边后，他们的距离的奇偶性就是 $i$ 到并查集根的奇偶性，异或 $j$ 到并查集根的奇偶性。连边的时候更新距离时，也这样计算即可。

时间复杂度 $O(nk+q\log q\log n)$，空间复杂度 $O(nk+q\log q)$。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,m,U[N],V[N],q,k,X[N],Y[N],lst[N],col[N],nxt[N];
pair<int,int>sta[N];
int top;
struct Bc{
    int fa[N],sz[N];
    bool dis[N];
    inline int find(int x){while(x!=fa[x])x=fa[x];return x;}
    inline int getdist(int x){int y=0;while(x!=fa[x])y^=dis[x],x=fa[x];return y;}
    void init(){
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    }
}g[52];
struct info{
    int x,y,col;
};
vector<info>vec[N<<2];
void add(int l,int r,int o,const int&L,const int&R,const int&u,const int&v,const int&cl){
    if(L<=l&&r<=R)
        vec[o].push_back((info){u,v,cl});
    else{
        const int mid=l+r>>1;
        if(L<=mid)add(l,mid,o<<1,L,R,u,v,cl);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,u,v,cl);
    }
}
void solve(int l,int r,int o){
    int TOP=top;
    for(int f=0;f<vec[o].size();++f){
        int cl=vec[o][f].col,u=vec[o][f].x,v=vec[o][f].y;
        int x=g[cl].find(u),y=g[cl].find(v);
        if(x!=y){
            if(g[cl].sz[x]<g[cl].sz[y])swap(x,y);
            g[cl].sz[x]+=g[cl].sz[y];
            g[cl].dis[y]=g[cl].getdist(u)^g[cl].getdist(v)^1;
            g[cl].fa[y]=x;
            sta[++top]=make_pair(cl,y);
        }
    }
    if(l==r){
        int id=X[l],cl=Y[l];
        int u=U[id],v=V[id];
        bool dis=g[cl].getdist(u)^g[cl].getdist(v)^1;
        if(dis&&g[cl].find(u)==g[cl].find(v)){
            cout<<"NO\n";
            if(l+1<=nxt[l])
                add(1,q,1,l+1,nxt[l],u,v,col[id]);
        }
        else{
            cout<<"YES\n";
            if(l+1<=nxt[l])
                add(1,q,1,l+1,nxt[l],u,v,col[id]=cl);
        }
    }else{
        const int mid=l+r>>1;
        solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
    }
    while(top>TOP){
        pair<int,int>f=sta[top--];
        int cl=f.first,y=f.second;
        g[cl].sz[g[cl].fa[y]]-=g[cl].sz[y];
        g[cl].dis[y]=0;
        g[cl].fa[y]=y;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>q;
    for(int i=1;i<=m;++i)
        cin>>U[i]>>V[i];
    for(int i=1;i<=q;++i){
        cin>>X[i]>>Y[i];
        if(lst[X[i]]){
            nxt[lst[X[i]]]=i;
        }
        lst[X[i]]=i;
    }
    for(int i=1;i<=q;++i)
        if(!nxt[i])nxt[i]=q;
    for(int i=1;i<=k;++i)g[i].init();
    solve(1,q,1);
    return 0;
}