【CF576E】Painting Edges
题意：给你一张n个点，m条边的无向图，每条边是k种颜色中的一种，满足所有颜色相同的边内部形成一个二分图。有q个询问，每次询问给出a,b代表将编号为a的边染成颜色b，但如果染色后不能满足所有颜色相同的边内部都是二分图就不染。问你每次是否能染成功。
$n,m,q\le 5\times 10^5,k\le 50$
题解：本题看起来要求在线，实质上完全可以离线。
如果没有不染这种操作的话，那么直接线段树按时间分治+并查集按秩合并就完事了。但如果有呢？我们先假设所有的都能染，那么每个操作都对应着线段树上的一段区间。在线段树处理到一个叶子时，如果发现不能染，那么就把这个操作对应的区间全都修改掉即可。时间复杂度还是一个log的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=500010;
int n,m,K,Q,top;
int pa[maxn],pb[maxn],last[maxn],pre[maxn],nxt[maxn],qa[maxn],qb[maxn],f[51][maxn],rnk[51][maxn];
bool g[51][maxn];
int sa[maxn],sb[maxn];
vector<int> v[maxn<<2];
vector<int>::iterator it;
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
int ret=0,f=1; char gc=nc();
while(!isdigit(gc)) {if(gc=='-') f=-f; gc=nc();}
while(isdigit(gc)) ret=ret*10+(gc^'0'),gc=nc();
return ret*f;
}
void updata(int l,int r,int x,int a,int b,int c)
{
if(a<=l&&r<=b)
{
v[x].push_back(c);
return ;
}
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b,c);
if(b>mid) updata(mid+1,r,rson,a,b,c);
}
void dfs(int l,int r,int x)
{
int now=top;
for(it=v[x].begin();it!=v[x].end();it++)
{
if(!qb[*it]) continue;
int x=pa[qa[*it]],y=pb[qa[*it]],z=qb[*it];
bool flag=1;
while(f[z][x]) flag^=g[z][x],x=f[z][x];
while(f[z][y]) flag^=g[z][y],y=f[z][y];
if(x==y) continue;
if(rnk[z][x]>rnk[z][y]) swap(x,y);
f[z][x]=y,g[z][x]=flag,sa[++top]=x,sb[top]=z;
if(rnk[z][x]==rnk[z][y]) rnk[z][y]++,sb[top]=-z;
}
if(l==r)
{
int x=pa[qa[l]],y=pb[qa[l]],z=qb[l];
bool flag=1;
while(f[z][x]) flag^=g[z][x],x=f[z][x];
while(f[z][y]) flag^=g[z][y],y=f[z][y];
if(x==y&&flag) qb[l]=qb[pre[l]],puts("NO");
else puts("YES");
while(top>now)
{
if(sb[top]<0) sb[top]=-sb[top],rnk[sb[top]][f[sb[top]][sa[top]]]--;
f[sb[top]][sa[top]]=0,top--;
}
return ;
}
int mid=(l+r)>>1;
dfs(l,mid,lson),dfs(mid+1,r,rson);
while(top>now)
{
if(sb[top]<0) sb[top]=-sb[top],rnk[sb[top]][f[sb[top]][sa[top]]]--;
f[sb[top]][sa[top]]=0,top--;
}
}
int main()
{
n=rd(),m=rd(),K=rd(),Q=rd();
int i;
for(i=1;i<=m;i++) pa[i]=rd(),pb[i]=rd();
for(i=1;i<=Q;i++)
{
qa[i]=rd(),qb[i]=rd();
if(last[qa[i]]) nxt[last[qa[i]]]=i,pre[i]=last[qa[i]];
last[qa[i]]=i,nxt[i]=Q+1;
}
for(i=1;i<=Q;i++) if(i+1<=nxt[i]-1) updata(1,Q,1,i+1,nxt[i]-1,i);
dfs(1,Q,1);
return 0;
}