CF576E Painting Edges

$\color{deeppink}link$

$n$ 个点，$m$ 条有颜色的边，共 $k$ 种颜色，一开始没有边有颜色，定义合法状态为保留每一颜色的所有的边，使得图是一个二分图。有 $q$ 次操作，判断每次操作后是否合法，若不合法则不操作。

$n,m,q\le 5\times 10^5,k\le 50$。

首先，$k$ 种颜色之间互不打扰，则可以对 $k$ 种颜色分别讨论看是否合法。

然后这道题就和 二分图 十分像了，但是我们无法知道一条边的消失时间。

若 $(u,v)$ 这条边在 $x,y$ 时间都操作了一遍，那么在 $(x,y)$ 的时间中，有两种情况：

• 操作 $x$
• 保留原来的颜色

那么可以将每个操作的消失时间设为下一个同样操作的时间 $-1$，然后再判断是否可以插入之后再在线段树上标记信息。

如何判断是否为二分图呢？

首先，二分图可用染色来判断，那么可以把个点拆成两个，要把 $u,v$ 加入并查集时，将 $s_u,t_v$ 合并，$t_u,s_v$ 合并来保证 $u,v$ 不同色，如果 $s_i,v_i$ 在同一集合中，则不是二分图。

在加入 $u,v$ 时，若 $s_u,s_v$ 已经在一个并查集中，则是不合法的。

还需要注意只有遍历到叶子节点时，才能加边和判断，且加边是不包括这个叶子的，因为若包含这个叶子，那在之后的几个叶子中可能加不到这个点的边，导致错误。若当前的颜色为 $0$，就代表这个边没有颜色，不用加。由于有 $k$ 个颜色，对于每一个点拆成 $2k$ 条边。

警钟敲烂：在加边的时候要写个函数，分开加，因为这题是合并两个并查集，所以可能在第一个并查集合并完后第二个并查集就不用合并了，两个点已在同一并查集中，再合并会死的瓜兮兮。调了一下午

时间是 $O(q\log q\log n)$。

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50,M=1e6+500;

struct node
{
	int u,v,c;
}e[M];

struct op
{
	int id,c;
}p[M];

struct wty
{
	int a,b,c;
}st[M<<1];

int n,m,k,q,fa[51][M],siz[51][M],la[M],top;
vector<int>edge[N];

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

inline void add(int x,int l,int r,int L,int R,int d)
{
	if(L<=l&&R>=r)return void(edge[x].push_back(d));
	if(L<=mid)add(ls,l,mid,L,R,d);
	if(R>mid)add(rs,mid+1,r,L,R,d);
}

inline int find(int x,int ty)
{
	return fa[ty][x]==x?x:find(fa[ty][x],ty);
}

inline void merge(int u,int v,int c)
{
	u=find(u,c),v=find(v,c);
	if(u==v)return;
	if(siz[c][u]>siz[c][v])swap(u,v);
	siz[c][v]+=siz[c][u];fa[c][u]=v;
	st[++top]=(wty){u,v,c};
}

inline void dfs(int x,int l,int r)
{
	int re=top;
	for(int i=0;i<(int)edge[x].size();i++)
	{
		int u=e[edge[x][i]].u,v=e[edge[x][i]].v,c=e[edge[x][i]].c;
		if(!c)continue;merge(v,u+n,c);merge(u,v+n,c);
	}
	if(l==r)
	{
		int id=p[l].id,u=e[id].u,v=e[id].v,c=p[l].c;
		u=find(u,c);v=find(v,c);
		if(u==v)puts("NO");
		else puts("YES"),e[id].c=c;
	}
	else dfs(ls,l,mid),dfs(rs,mid+1,r);
	while(top>re)
	{
		int aa=st[top].a,bb=st[top].b,cc=st[top].c;
		siz[cc][bb]-=siz[cc][aa];fa[cc][aa]=aa;
		top--;
	}
	return;
}

char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;inline int read(){
	while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
	while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}

main()
{
	n=read(),m=read(),k=read(),q=read();
	for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),la[i]=q+1;
	for(int i=1;i<=q;i++)p[i].id=read(),p[i].c=read();
	for(int i=1;i<=k;i++)
	for(int j=1;j<=2*n;j++)
	fa[i][j]=j,siz[i][j]=1;
	for(int i=q;i>=1;i--)
	{
		if(i!=q)add(1,1,q,i+1,la[p[i].id]-1,p[i].id);
		la[p[i].id]=i;
	}
	dfs(1,1,q);
}