Painting Edges[CF576E][线段树分治][并查集]

题目

Luogu

思路

你会发现和这道没什么区别
Bipartite Checking
相关题解：
Bipartite Checking题解
发现颜色数量很少，我们就每次建立 $k$ 个 $DSU$ 一起跑即可
记每个操作影响范围为现在到下一次这条边修改之前
问题是每个操作影响范围 $[L,R]$ 只有当合法才会进行
怎么办？
接下来跟这道题思路非常像，暂且称为延迟操作吧
玄学

肯定是按照 $1?n$ 访问叶子，不需要开始将操作都打到线段树上

可以访问完一个叶子判断合法性后，再打这个叶子对应的操作区间 $[L+1,R]$
然后就可以做了
时间复杂度：线段树上有 $nlogn$ 个修改操作，并查集有按秩合并每次是 $logn$ 的，有 $k$ 个 $DSU$
总时间复杂度 $O(knlo{g}^{2}n)$

代码

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline LL read() {
    bool f=0;LL x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 500000
#define INF 100000000000000ll
int n,m,k,q,U[MAXN+5],V[MAXN+5],nxt[MAXN+5],Id[MAXN+5],C[MAXN+5],E[MAXN+5];
struct DSU{
    int tp,Stk[MAXN+5];int fa[MAXN+5],c[MAXN+5],dep[MAXN+5];int Find(int u){
    return fa[u]==u?u:Find(fa[u]);}int Dis(int u){
    return fa[u]==u?0:(Dis(fa[u])^c[u]);}bool check(int id){
    int u=Find(U[id]),v=Find(V[id]);int cu=Dis(U[id]),cv=Dis(V[id]);return u!=v||(cu^cv);}void Init(int n){
    tp=0;for(int i=1;i<=n;i++)fa[i]=i,c[i]=0,dep[i]=0;return ;}void Merge(int u,int v){
    int cu=Dis(u),cv=Dis(v);u=Find(u),v=Find(v);if(u==v) return ;if(dep[u]<dep[v]) swap(u,v);else if(dep[u]==dep[v])dep[u]++,Stk[++tp]=-u;fa[v]=u,c[v]=cu^cv^1,Stk[++tp]=v;return ;}void Restore(int ntp){
    while(tp>ntp){
    if(Stk[tp]<0) dep[-Stk[tp]]--;else fa[Stk[tp]]=Stk[tp],c[Stk[tp]]=0;tp--;}return ;}
}S[51];
#define lch (rt<<1)
#define rch (rt<<1|1)
#define mp make_pair
struct node{
    int u,v,c;};
vector<node>tree[5*MAXN+5];
void Insert(int rt,int L,int R,int qL,int qR,node x){
    if(qL<=L&&R<=qR){
    tree[rt].push_back(x);return ;}int Mid=(L+R)>>1;if(qL<=Mid)Insert(lch,L,Mid,qL,qR,x);if(Mid+1<=qR)Insert(rch,Mid+1,R,qL,qR,x);return ;
}
void DFS(int rt,int L,int R){
    int ntp[50]={
    0};for(int i=1;i<=k;i++)ntp[i]=S[i].tp;for(int i=0;i<(int)tree[rt].size();i++)S[tree[rt][i].c].Merge(tree[rt][i].u,tree[rt][i].v);if(L==R){
    if(S[C[L]].check(Id[L]))E[Id[L]]=C[L],puts("YES");else puts("NO");Insert(1,1,q,L+1,nxt[L],(node){
    U[Id[L]],V[Id[L]],E[Id[L]]});for(int i=1;i<=k;i++)S[i].Restore(ntp[i]);return ;}int Mid=(L+R)>>1;DFS(lch,L,Mid),DFS(rch,Mid+1,R);for(int i=1;i<=k;i++)S[i].Restore(ntp[i]);return ;
}
map<int,int> Map;
int main(){
    n=read(),m=read(),k=read(),q=read();for(int i=1;i<=k;i++)S[i].Init(n);for(int i=1;i<=m;i++)U[i]=read(),V[i]=read();for(int i=1;i<=q;i++){
    Id[i]=read(),C[i]=read();if(Map.count(Id[i]))nxt[Map[Id[i]]]=i-1;Map[Id[i]]=i;}for(map<int,int>::iterator it=Map.begin();it!=Map.end();it++)nxt[it->second]=q;DFS(1,1,q);return 0;
}

思考

代码量大时，一定要学会静态查错，可以理清思路后调整状态再看代码，比如编号 $i$ 和 $i{d}_i$ 这种定义不明确时就容易弄混