自动搬运

查看原文

来自洛谷，原作者为

	Arghariza Delightful.

搬运于2025-08-24 22:23:03，当前版本为作者最后更新于2023-09-06 08:57:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

整体二分。

有个小技巧，就是可以把存边的数组往后复制一遍，然后删去区间 $[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;
}