[CF576E] Painting Edges

Painting Edges
动态加边和二分图容易想线段树分治,分别维护 k 种颜色的并查集。
不过每条边的存在时间不能确定。
设边 i 的两次操作的时间为 \(x_i,y_i\),那么对于 \(t\in[x_i+1,y_i-1]\) 有两种情况,颜色改变或改色不变。
则我们把每次操作影响的时间放在树上,从左到右递归到叶子节点判断染色结果即可。
注意不能把 \(x_i\) 放上去,因为这时还不清楚染色是否成功。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define ls p<<1
#define rs p<<1|1
#define b1t bitset
#define mkp make_pair
typedef pair<int,int> kk;
const int MAXN=5e5+5;
const int MAXK=55;
const int INF=0x3f3f3f3f;
void read(int &x){
	x=0;int f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);s=getchar();
	}
	x*=f;
}
int n,m,k,q,vva[MAXN],vvb[MAXN],vv[MAXN],va[MAXN],vb[MAXN],c[MAXN],fa[MAXK][MAXN<<1],id[MAXN],siz[MAXK][MAXN<<1],tp;
int Find(int co,int x){return x==fa[co][x]?x:Find(co,fa[co][x]);}
struct SG{
	int l,r;vector<int> ve;
}t[MAXN<<2];
kk ss[MAXN<<1],ff[MAXN<<1];
int cc[MAXN<<1];
void bui(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	bui(ls,l,mid);bui(rs,mid+1,r);	
}
void mer(int c,int x,int y){
	if(x==y) return;
	if(siz[c][x]>siz[c][y]) swap(x,y);
	ss[++tp]=mkp(y,siz[c][y]),ff[tp]=mkp(x,fa[c][x]);cc[tp]=c;
	siz[c][y]+=siz[c][x];fa[c][x]=y;
}
void modi(int p,int l,int r,int x){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].ve.push_back(x);return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) modi(ls,l,r,x);
	if(r>mid) modi(rs,l,r,x);
}
void work(int p){
	int op=tp;
	for(auto u:t[p].ve){
		mer(c[u],Find(c[u],va[u]),Find(c[u],vb[u]+n));
		mer(c[u],Find(c[u],va[u]+n),Find(c[u],vb[u]));
	}
	if(t[p].l==t[p].r){
		if(Find(c[t[p].l],va[t[p].l])==Find(c[t[p].l],vb[t[p].l])) c[t[p].l]=id[vv[t[p].l]],printf("NO\n");
		else id[vv[t[p].l]]=c[t[p].l],printf("YES\n");
	}
	else{
		work(ls);work(rs);
	}
	while(tp>op){
		siz[cc[tp]][ss[tp].first]=ss[tp].second;
		fa[cc[tp]][ff[tp].first]=ff[tp].second;
		tp--;
	}
	return;
}
int main(){
	read(n);read(m);read(k);read(q);
	for(int ii=1;ii<=k;ii++){
		for(int i=1;i<=n;i++){
			fa[ii][i]=i;fa[ii][i+n]=i+n;siz[ii][i]=siz[ii][i+n]=1;
		}
	}
	for(int i=1;i<=m;i++){
		read(vva[i]);read(vvb[i]);id[i]=q+1;
	}
	for(int i=1;i<=q;i++){
		read(vv[i]);read(c[i]);va[i]=vva[vv[i]];vb[i]=vvb[vv[i]];
	}
	bui(1,1,q);
	for(int i=q;i>=1;i--){
		if(i+1<id[vv[i]]) modi(1,i+1,id[vv[i]]-1,i);
		id[vv[i]]=i;
	}
	for(int i=1;i<=q;i++) id[i]=0;
	work(1);
	return 0;
}