WAon10 727求助

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 5e5 + 5; 
#define ls u << 1
#define rs u << 1 | 1
 
int n, m, k, top, p[maxn], q;
int U[maxn], V[maxn], A[maxn], C[maxn], fa[55][maxn << 1], h[55][maxn << 1];
vector<int> t[maxn << 2];
struct node {
	int c, x, y, val;
} a[maxn << 2];
 
inline int Find(int x, int c) {
	return (x == fa[c][x] ? x : Find(fa[c][x], c));
}
 
inline void merge(int x, int y, int c) {
	x = Find(x, c);
	y = Find(y, c);
	if (x == y) {
		return;
	}
	if (h[c][x] > h[c][y]) {
		swap(x, y);
	}
	fa[c][x] = y;
	a[++top] = {c, x, y, h[c][x] == h[c][y]}; 
	if (h[c][x] == h[c][y]) {
		++h[c][y];
	}
}
 
inline void update(int u, int l, int r, int L, int R, int w) {
	if (l <= L && R <= r) {
		t[u].push_back(w);
		return;
	} else {
		int mid = (L + R) >> 1;
		if (l <= mid) {
			update(ls, l, r, L, mid, w);
		} 
		if (r > mid) {
			update(rs, l, r, mid + 1, R, w);
		} 
	}
}
 
inline void solve(int u, int l, int r) {
	bool flag = false;
	int lst = top;
	for (auto i : t[u]) {
		int id = A[i];
		int x = U[id];
		int y = V[id];
		int c = C[i];
		if (!c) {
			continue;
		}
		merge(x, y + n, c);
		merge(y, x + n, c);
	}
	if (!flag) {
		if (l == r) {
			int c = C[l];
			int d = A[l]; 
			if (Find(U[d], c) == Find(V[d], c) || Find(U[d] + n, c) == Find(V[d] + n, c)) {
				cout << "NO\n";
				C[l] = p[d];
			} else {
				cout << "YES\n";
				p[d] = C[l];
			}
			
		} else {
			int mid = (l + r) >> 1;
			solve(ls, l, mid);
			solve(rs, mid + 1, r);
		} 
	} 
	for(int i = top; i > lst; --i) {
		int c = C[a[i].c];
		fa[c][a[i].x] = a[i].x;
		h[c][a[i].y] -= a[i].val;
	}
	top = lst;
}
 
inline void calc() {
	cin >> n >> m >> k >> q;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j) {
			fa[j][i] = i;
			fa[j][i + n] = i + n;
		}
	}
	for (int i = 1; i <= m; ++i) {
		cin >> U[i] >> V[i];
		p[i] = q + 1;
	}
	for (int i = 1; i <= q; ++i) {
		cin >> A[i] >> C[i];
	}
	
	for (int i = q; i >= 1; --i) {
		int x = A[i];
		if (i < p[x] - 1) {
			update(1, i + 1, p[x] - 1, 1, q, i);
		}
		p[x] = i;
	}
	for (int i = 1; i <= m; ++i) {
		p[i] = 0;
	}
	solve(1, 1, q);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    calc();
 
    return 0;
}