BalticOI 2020 Day1 小丑

· · 题解

整体二分。

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