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;
}