洛谷P5787 【模板】线段树分治题解

题意：

cxy 有一个 \(n\) 个节点的图。

因为 cxy 是 cxy，所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。

cxy 要求出每一时间段内这个图是否是二分图。

这么简单的问题 cxy 当然会做了，于是她想考考你。

输入格式：

第一行三个整数 \(n,m,k\)。

接下来 \(m\) 行，每行四个整数 \(x,y,l,r\)，表示有一条连接 \(x,y\) 的边在 \(l\) 时刻出现 \(r\) 时刻消失。

输出格式：

共 \(k\) 行，第 \(i\) 行一个字符串 Yes 或 No，表示在第 \(i\) 时间段内这个图是否是二分图。

数据范围：

\(1\le n,k \le 10^5,~1 \le m \le 2\times 10^5,~1 \le x,y \le n,~0 \le l \le r \le k\)。

本题是线段树分治的模板题。

线段树分治其实非常简单。考虑对时间轴建立线段树，每个节点维护这段区间存在的边集。

因为如果区间 \([l,r]\) 有一条边存在，那么任意区间 \(S \subseteq [l,r]\) 这条边都存在，

所以我们只需要在深度最小的那个节点存这条边即可（用 vector 维护即可）

现在考虑对这棵线段树进行 dfs ，那么我们需要一个可以回溯，且可以判断原图有没有奇环的数据结构。

考虑扩展域并查集（种类并查集），还需要加一个常见的并查集撤销操作。

简单讲一下。种类并查集就是把每个点看作两个位于不同集合中的点。

记这两个点集是 \(S,T\) ，每次加入新边 \((u,v)\) ，我们分别把 \(S_u,T_v\) 以及 \(S_v,T_u\) 合并

如果原图不存在奇环，那么 \(S\) 中任意一点 \(u\) ，不存在任意 \(v \in T\) 满足 \(u,v\) 在并查集的同一集合内。

然后撤销操作只需要用按秩合并的时候用一个栈记录一下合并了哪两个节点之类的信息即可。

时间复杂度 \(\mathcal{O}(n \log n \log T)\) ，注意可撤销并查集不能用路径压缩。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define M ((int)(2e5 + 15))
#define pb push_back
#define Fi first
#define Se second
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, m, T;
vector<int> tr[N * 4]; pii e[M]; stack<pii> stk;
namespace DSU
{
    int f[N * 2], r[N * 2];
    void init(int n) { rep(i, 1, n) { f[i] = i, f[i + n] = i + n; } }
    int find(int x) { return f[x] == x ? x : find(f[x]); }
    void merge(int x, int y)
    {
        if(x == y) return; if(r[x] > r[y]) swap(x, y);
        stk.push({x, r[x] == r[y]}); f[x] = y; r[y] += (r[x] == r[y]);
    }
} using DSU::find; using DSU::merge; using DSU::init;
void update(int nl, int nr, int k, int l = 1, int r = T, int at = 1)
{
    if(nl <= l && r <= nr) { return tr[at].pb(k), void(0); }
    int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
}
void solve(int nl, int nr, int l = 1, int r = T, int at = 1)
{
    bool ok = true; int o = stk.size();
    for(int i : tr[at])
    {
        int u = e[i].Fi, v = e[i].Se;
        if(find(u) == find(v)) { rep(j, l, r) { cout << "No\n"; } ok = false; break; }
        merge(find(u + n), find(v)); merge(find(u), find(v + n));
    }
    if(ok)
    {
        if(l == r) cout << "Yes\n";
        else
        {
            int mid = (l + r) >> 1;
            solve(nl, nr, l, mid, ls(at));
            solve(nl, nr, mid + 1, r, rs(at));
        }
    }
    while(stk.size() > o)
    {
        DSU::r[DSU::f[stk.top().Fi]] -= stk.top().Se;
        DSU::f[stk.top().Fi] = stk.top().Fi; stk.pop();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> T;
    rep(i, 1, m)
    {
        static int l, r;
        cin >> e[i].Fi >> e[i].Se >> l >> r;
        if(l != r) update(l + 1, r, i);
    }
    init(n); solve(1, T);
    return 0;
}