类比一下模板题，其实我们只需要把扩展域并查集再扩展成 \(k\) 个即可
但有个问题，当改变一条边的颜色，导致不能构成二分图时，我们就不能操作；但在线段树上，我们的操作不一定是严格按照时间的
我们考虑对颜色的生效时间范围做一些改动：如果一条边的这种颜色出现的时间是 \(x\)，被改变的时间是 \(y\)，那么我们就添加到 \([l+1,r-1]\) 区间的线段树上
这样的话，当我们递归到叶子结点 \(l=r\) 时，那么时间 \(l\) 前的操作的已经做完了，这时候我们就只需要判断第 \(l\) 个操作是否合法即可。
如果合法，我们就记录这条改动的边的当前颜色为第 \(l\) 个操作的颜色；
否则，我们就把这次操作的颜色改成这条改动的边的当前颜色
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define ls (now << 1)
#define rs ((now << 1) | 1)
inline int reads()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, k, q, lst[500005];
struct Node
{
int x, y;
}e[500005];
struct Modify
{
int id, cl;
}c[500005];
int fa[55][1000005], dep[55][1000005];
std::vector<int> tr[2000005];
void add(int now, int l, int r, int L, int R, int id)
{
if(L <= l && r <= R)
{
tr[now].emplace_back(id);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) add(ls, l, mid, L, R, id);
if(mid < R) add(rs, mid + 1, r, L, R, id);
}
struct ST
{
int cl, x, y, dep;
}stk[1000005]; int scnt;
inline int finds(int cl, int now)
{
while(fa[cl][now] ^ now) now = fa[cl][now];
return now;
}
inline void merge(int cl, int x, int y)
{
x = finds(cl, x), y = finds(cl, y);
if(x == y) return;
if(dep[cl][x] > dep[cl][y]) std::swap(x, y);
stk[++scnt] = (ST){cl, x, y, dep[cl][x] == dep[cl][y]};
fa[cl][x] = y;
dep[cl][y] += stk[scnt].dep;
}
inline void Del(int la)
{
while(scnt > la)
{
int cl = stk[scnt].cl, x = stk[scnt].x, y = stk[scnt].y;
dep[cl][y] -= stk[scnt].dep;
fa[cl][x] = x;
scnt--;
}
}
void solve(int now, int l, int r)
{
int lacnt = scnt;
for(int i : tr[now])
if(c[i].cl)
merge(c[i].cl, e[c[i].id].x, e[c[i].id].y + n),
merge(c[i].cl, e[c[i].id].y, e[c[i].id].x + n);
if(l == r)
{
if(finds(c[l].cl, e[c[l].id].x) == finds(c[l].cl, e[c[l].id].y))
puts("NO"), c[l].cl = lst[c[l].id];
else puts("YES"), lst[c[l].id] = c[l].cl;
Del(lacnt);
return;
}
int mid = (l + r) >> 1;
solve(ls, l, mid), solve(rs, mid + 1, r);
Del(lacnt);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = reads(), m = reads(), k = reads(), q = reads();
FOR(i, 1, m) e[i] = (Node){reads(), reads()}, lst[i] = q + 1;
FOR(i, 1, q) c[i] = (Modify){reads(), reads()};
FOR(i, 1, k) FOR(j, 1, n) fa[i][j] = j, fa[i][j + n] = j + n, dep[i][j] = dep[i][j + n] = 1;
ROF(i, q, 1)
{
if(i < lst[c[i].id] - 1) add(1, 1, q, i + 1, lst[c[i].id] - 1, i);
lst[c[i].id] = i;
}
FOR(i, 1, m) lst[i] = 0;
solve(1, 1, q);
return 0;
}