题目
分析：
从前天早上肝到明天早上qwq其实颓了一上午MC ，自己瞎yy然后1A，写篇博客庆祝一下。
首先做这题之前推荐一道很相似的题：【BZOJ4025】二分图（可撤销并查集+线段树分治）
大力每个颜色维护一个并查集，就很像上面那道题了。但是存在一个问题：在处理线段树区间([l,r])时，可能并不知道(l)处的修改是否成功，所以不知道(l)处修改的边具体是什么颜色的。
我的解决方案是：处理区间([l,r])时忽略(l)处修改的边。先向左子树递归，递归到叶子时判断本次修改颜色能否成功。然后回溯后向右子树递归前将这条边加入。
代码：
solve函数的第四个参数表示现在是否已经忽略了(l)处修改的边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <bitset>
#include <stack>
using namespace std;
namespace zyt
{
template<typename T>
inline void read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != '-' && !isdigit(c));
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-'), x = -x;
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
inline void write(const char *const s)
{
printf("%s", s);
}
const int N = 5e5 + 10, B = 19, K = 51;
int n, m, k, q, head[1 << (B + 1) | 11], ecnt;
struct UFS
{
int fa[N], rk[N];
bitset<N> dis;
struct node
{
UFS &ufs;
int x, y, fa, rk, dis;
};
static stack<node> sta;
inline void init()
{
for (int i = 0; i < N; i++)
fa[i] = i, rk[i] = 1;
dis = 0U;
}
int f(const int x)
{
return x == fa[x] ? x : f(fa[x]);
}
int dist(const int x)
{
return x == fa[x] ? dis[x] : dist(fa[x]) ^ dis[x];
}
inline bool merge(const int u, const int v)
{
int x = f(u), y = f(v);
if (x == y)
return dist(u) ^ dist(v);
if (rk[x] > rk[y])
swap(x, y);
sta.push((node){*this, x, y, fa[x], rk[y], dis[x]});
fa[x] = y, dis[x] = dis[x] ^ dist(u) ^ dist(v) ^ 1;
if (rk[x] == rk[y])
++rk[y];
return true;
}
static inline int set_undo()
{
return sta.size();
}
static inline void undo(const int bck)
{
while (sta.size() > bck)
{
UFS &now = sta.top().ufs;
now.fa[sta.top().x] = sta.top().fa;
now.rk[sta.top().y] = sta.top().rk;
now.dis[sta.top().x] = sta.top().dis;
sta.pop();
}
}
}ufs[K];
stack<UFS::node> UFS::sta;
struct edge
{
int id, next;
}e[N * B];
inline void add(const int a, const int b)
{
e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++;
}
struct ed
{
int u, v;
}arr[N];
struct node
{
int ed, col;
}mdf[N];
int pre[N], nxt[N], last[N];
namespace Segment_Tree
{
void insert(const int rot, const int lt, const int rt, const int ls, const int rs, const int id)
{
if (ls <= lt && rt <= rs)
{
add(rot, id);
return;
}
int mid = (lt + rt) >> 1;
if (ls <= mid)
insert(rot << 1, lt, mid, ls, rs, id);
if (rs > mid)
insert(rot << 1 | 1, mid + 1, rt, ls, rs, id);
}
void solve(const int rot, const int lt, const int rt, bool flag)
{
int mid = (lt + rt) >> 1;
int bck = UFS::set_undo();
bool f = false;
for (int i = head[rot]; ~i; i = e[i].next)
{
int now = e[i].id;
if (lt == now)
{
flag = true;
continue;
}
UFS &u = ufs[mdf[now].col];
ed &edg = arr[mdf[now].ed];
if (mdf[now].col)
u.merge(edg.u, edg.v);
}
if (lt == rt)
{
if (!ufs[mdf[lt].col].merge(arr[mdf[lt].ed].u, arr[mdf[lt].ed].v))
mdf[lt].col = mdf[pre[lt]].col, write("NO");
else
write("YES");
putchar('
');
}
else
{
solve(rot << 1, lt, mid, f | flag);
if (f | flag)
ufs[mdf[lt].col].merge(arr[mdf[lt].ed].u, arr[mdf[lt].ed].v);
solve(rot << 1 | 1, mid + 1, rt, false);
}
UFS::undo(bck);
}
}
int work()
{
using namespace Segment_Tree;
memset(head, -1, sizeof(head));
read(n), read(m), read(k), read(q);
for (int i = 1; i <= k; i++)
ufs[i].init();
for (int i = 1; i <= m; i++)
read(arr[i].u), read(arr[i].v);
for (int i = 1; i <= q; i++)
{
read(mdf[i].ed), read(mdf[i].col);
nxt[i] = q + 1;
}
for (int i = 1; i <= q; i++)
{
if (last[mdf[i].ed])
pre[i] = last[mdf[i].ed];
last[mdf[i].ed] = i;
}
for (int i = q; i > 0; i--)
nxt[pre[i]] = i;
for (int i = 1; i <= q; i++)
insert(1, 1, q, i, nxt[i] - 1, i);
solve(1, 1, q, false);
return 0;
}
}
int main()
{
return zyt::work();
}