整体二分。
有个小技巧,就是可以把存边的数组往后复制一遍,然后删去区间 \([l,r]\) 就相当于保留区间 \([r+1,l+m-1]\) 的边。于是只需要解决这么个问题:
给定一张 \(n\) 个点 \(m\) 条边的无向图,\(q\) 次询问,每次只保留区间 \([l,r]\) 的边,问是否是二分图。
乍一看有点像 Cnoi2019 须臾幻境?但是其实有不用 LCT 的做法。
考虑令 \(f_l\) 表示最小的 \(p\) 使得 \([l,p]\) 区间不是二分图。显然 \(f\) 具有单调性,即 \(\forall i\le i',f_i\le f_{i'}\)。只需要求出所有的 \(f_i\),就可以直接根据 \(f_l\) 是否 \(\le r\) 判断是否是二分图了。
由于 \(f\) 的单调性,不难想到整体二分。令 \(S(l,r,v_l,v_r)\) 表示处理 \(f_{l},f_{l+1},\cdots, f_{r}\),并且 \(v_l\le f_l\le f_r\le v_r\)。令 \(\text{mid}=\frac{l+r}{2}\),于是只需要求出 \(f_{\text{mid}}\) 即可:用可撤销并查集从 \(\text{mid}\) 开始加边,第一个使得图不是二分图的位置就是 \(f_\text{mid}\)。
为了保证复杂度,需要在分治之前将 \((r,v_l)\) 的边先加进并查集中。然后就没什么细节了。
复杂度 \(O(m\log m\log n+q)\),整体二分复杂度写假的是小丑。
// Problem: Joker
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1386C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 2e5 + 200;
int n, m, q, tp, st[N << 1], fa[N << 1], sz[N << 1], f[N];
pi p[N << 1];
int gf(int x) { return x == fa[x] ? x : gf(fa[x]); }
void mrg(int x, int y) {
x = gf(x), y = gf(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
fa[y] = x, sz[x] += sz[y], st[++tp] = y;
}
void del(int s) {
while (tp > s) {
int y = st[tp--];
sz[fa[y]] -= sz[y], fa[y] = y;
}
}
bool link(int x, int y) {
mrg(x, y + n), mrg(y, x + n);
if (gf(x) == gf(y)) return 0;
return 1;
}
void conq(int l, int r, int s, int t) {
if (l > r || s > t) return;
if (s == t) {
for (int i = l; i <= r; i++) f[i] = s;
return;
}
int mid = (l + r) >> 1, sz = tp;
for (int i = mid; i <= r; i++)
if (!link(p[i].fi, p[i].se)) { f[mid] = i; break; }
if (!f[mid])
for (int i = max(s, r + 1); i <= t; i++)
if (!link(p[i].fi, p[i].se)) { f[mid] = i; break; }
del(sz);
for (int i = mid; i < min(s, r + 1); i++) link(p[i].fi, p[i].se);
conq(l, mid - 1, s, f[mid]), del(sz);
for (int i = max(s, r + 1); i < f[mid]; i++) link(p[i].fi, p[i].se);
conq(mid + 1, r, f[mid], t), del(sz);
}
int main() {
n = rd(), m = rd(), q = rd();
for (int i = 1; i <= n << 1; i++) fa[i] = i, sz[i] = 1;
for (int i = 1, u, v; i <= m; i++)
u = rd(), v = rd(), p[i] = p[i + m] = mp(u, v);
conq(1, m + 1, 1, m << 1 | 1);
while (q--) {
int l = rd(), r = rd();
if (f[r + 1] <= m + l - 1) puts("YES");
else puts("NO");
}
return 0;
}