[洛谷P5787] 线段树时间分治

题目大意

给 \(n\) 个点 \(m\) 条边，在 \(k\) 时间内，第 \(i\) 条边只在 \([l_i+1,r_i]\) 的时间范围内存在。对于每个 \(i\leq k\)，输出 \(i\) 时刻这个图是否是二分图。

题解

因为每条边只在一个范围的时间内存在，我们可以对时间轴建线段树，线段树的每个结点维护一个vector，里面存这个时间段内哪些边是存在的。一条边会被划分成 \(O(\log k)\) 个线段树上的区间段中，也就是只会加入 \(O(\log k)\) 个 vector 中。判二分图可以用扩展域并查集来做。对于询问 \(i\) 时刻是否是二分图，我们在扩展域并查集中加入从线段树的根到询问的叶子结点这一路径上所有的 vector 中的边。在回溯时要把加入的边删掉，所以需要可撤销并查集。时间复杂度 \(O(m\log n\log k)\)。

Code

#include <bits/stdc++.h>
using namespace std;

#define LL long long

template<typename elemType>
inline void Read(elemType& T) {
    elemType X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-';ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    T = (w ? -X : X);
}

const int maxn = 200005;

struct UFS {
    int f[maxn << 1], rk[maxn << 1];
    stack<pair<int, int>> opt;
    int find(int u) {
        while (u ^ f[u]) u = f[u];
        return u;
    }
    void merge(int u, int v) {
        if ((u = find(u)) == (v = find(v))) return;
        if (rk[u] > rk[v]) swap(u, v);
        opt.push(make_pair(u, rk[u] == rk[v]));
        f[u] = v; rk[v] += (rk[u] == rk[v]);
    }
    void undo() {
        int u = opt.top().first;
        rk[f[u]] -= opt.top().second;
        f[u] = u; opt.pop();
    }
};
UFS S;
int u[maxn], v[maxn];
int n, m, k;

vector<int> T[maxn << 2];

void insert(int rt, int L, int R, int QL, int QR, int x) {
    if (R < QL || QR < L) return;
    if (QL <= L && R <= QR) { T[rt].push_back(x); return; }
    int mid = (L + R) >> 1;
    insert(rt << 1, L, mid, QL, QR, x);
    insert(rt << 1 | 1, mid + 1, R, QL, QR, x);
}

void DFS(int rt, int L, int R) {
    bool ok = true;
    int sz = S.opt.size();
    for (auto x : T[rt]) {
        int u = S.find(::u[x]), v = S.find(::v[x]);
        if (u == v) {
            for (int i = L;i <= R;++i) printf("No\n");
            ok = false;
            break;
        }
        S.merge(::u[x] + n, v);
        S.merge(::v[x] + n, u);
    }
    if (ok) {
        if (L == R) { printf("Yes\n"); return; }
        int mid = (L + R) >> 1;
        DFS(rt << 1, L, mid);
        DFS(rt << 1 | 1, mid + 1, R);
    }
    while (S.opt.size() > sz) S.undo();
}

int main() {
    Read(n); Read(m); Read(k);
    for (int i = 1;i <= m;++i) {
        int l, r;
        Read(u[i]); Read(v[i]); Read(l); Read(r);
        if (l != r) insert(1, 1, k, l + 1, r, i);
    }
    for (int i = 1;i <= n * 2;++i) S.f[i] = i;
    DFS(1, 1, k);

    return 0;
}