CF576E Painting Edges
关于我看完题解后改了一个位置就过题导致我都不知道我怎么过的
当然现在真的大彻大悟了。
题意
给定一张 \(n\) 个点，\(m\) 条边无向图，有 \(k\) 种颜色，初始每条边无颜色，给定 \(q\) 个操作，每个操作某条边染成颜色 \(c\)。只有一个操作合法，我们才能真正执行该操作，否则不执行。一个操作合法，当且仅当执行完所得的图，保留任意一种颜色的边（不包括无色边）所得的子图是二分图。求出每次操作是否会执行。
思路
首先观察到颜色数非常少，可以考虑对每个点都开 \(k\) 个并查集，利用并查集判断是否出现奇环；我们把所有操作都看作加边，然后就可以利用线段树分治模板（这道题)的思路解决了……
吗？
我们会发现这道题有一个不一样的地方：有些操作是无法执行的，这导致我们一开始挂上线段树的操作可能需要撤回。
显然，直接删除是不现实的。我们可以将删除改为维持原状，即把不合法的修改变成上一个合法修改。
然后，我们发现，对于每一个时间点我我们都只对应一个操作，这一个性质非常重要。我们对线段树 dfs 的时候，也是按照时间顺序去访问每个叶子节点的，也就是说，当我们访问到一个叶子节点的时候，会把之前的所有合法操作执行完，同时可以知道这个时刻对应的操作！
同样因为时序性，每个叶子节点的操作都应该最后被执行，那我们就可以考虑把第 \(i\) 次修改与第 \(j\) 次修改之间，\(i\) 次修改的作用区域设为 \([i+1, j-1]\)。\(j-1\) 好理解，那 \(i+1\) 呢？这一步转化就是在保证之前所有的合法修改执行完才进行第 \(i\) 次修改，因为在这里需要先进行判断，如果合法才可以执行，而是否执行第 \(i\) 次修改并不影响判断。
这样，我们的问题就解决了。每次遍历到一个叶子节点，先进行判断，如果不合法，就把这个操作改成上一次操作后的颜色。
代码：
#include<bits/stdc++.h>
#define ls tr<<1
#define rs tr<<1 | 1
using namespace std;
const int N = 5e5+100;
inline int read(){
int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
return x;
}
struct Edge{
int u, v;
}e[N];
struct Node{
int tk, c;
}op[N];
struct Revoke{
int c, u, del;
};
stack<Revoke> s;
int top;
int fa[55][N<<1], dep[55][N<<1];
int n, m, K, Q;
vector<int> tree[N<<2];
void insert(int tr, int L, int R, int lq, int rq, int tk){
if(L == lq && rq == R){
tree[tr].push_back(tk);
return;
}
int mid = (L+R)>>1;
if(lq<=mid) insert(ls, L, mid, lq, min(rq, mid), tk);
if(rq> mid) insert(rs, mid+1, R, max(lq, mid+1), rq, tk);
}
inline int find(int x, int col){
while(x!=fa[col][x]) x = fa[col][x];
return x;
}
void merge(int col, int x, int y){
int fx = find(x, col), fy = find(y, col);
if(fx == fy) return;
if(dep[col][fx]>dep[col][fy]) swap(fx, fy);
++top;
Revoke tmp = (Revoke){col, fx, dep[col][fx] == dep[col][fy]};
s.push(tmp);
fa[col][fx] = fy;
dep[col][fy]+=(dep[col][fx] == dep[col][fy]);
}
bool ans[N];
int lstcol[N];
void solve(int tr, int L, int R){
int last = s.size();
for(int i = 0; i<tree[tr].size(); ++i){
int opi = tree[tr][i];
if(!op[opi].c) continue;//如果没有颜色就不进行修改
int u = e[op[opi].tk].u, v = e[op[opi].tk].v;
int col = op[opi].c;
merge(col, u, v+n);
merge(col, v, u+n);
}
if(L == R){//当我们遍历到叶子节点的时候，这个时刻对应的操作是未被执行的
//而之前所有的合法操作都已经执行完毕，因此这时候是可以判断该次操作是否合法
int col = op[L].c, tk = op[L].tk;
int x = e[tk].u, y = e[tk].v;
if(find(x, col) == find(y, col)){
puts("NO");
op[L].c = lstcol[tk];//如果不合法，直接把这次操作改为上次操作的颜色
} else{
puts("YES");
lstcol[tk] = op[L].c;//记录最后一次合法修改的颜色
}
} else{
int mid = (L+R)>>1;
solve(ls, L, mid);
solve(rs, mid+1, R);
}
while(s.size()>last){
Revoke tmp = s.top();
s.pop();
int col = tmp.c, u = tmp.u, del = tmp.del;
dep[col][fa[col][u]]-=del;
fa[col][u] = u;
}
}
int las[N];
int tot;
int main(){
n = read(), m = read(), K = read(), Q = read();
for(int i = 1; i<=m; ++i){
e[i].u = read(), e[i].v = read();
}
for(int i = 1; i<=Q; ++i){
op[i].tk = read(), op[i].c = read();
if(las[op[i].tk] && las[op[i].tk]<i-1){
insert(1, 1, Q, las[op[i].tk]+1, i-1, las[op[i].tk]);
}
las[op[i].tk] = i;
}
for(int i = 1; i<=m; ++i){
if(las[i]<Q){
insert(1, 1, Q, las[i]+1, Q, las[i]);
}
}
for(int i = 1; i<=K; ++i){
for(int j = 1; j<=n*2; ++j){
fa[i][j] = j;
}
}
solve(1, 1, Q);
return 0;
}