线段树分治学习笔记附加可撤销并查集

· · 个人记录

额， 我又来写学习笔记了。 首先放个题目链接得勒。 可恶的题目

前置知识1：可撤销并查集

看完题目我们肯定会想到用并查集来解决，我们一般的做法是路径压缩，可是这样就没办法撤销了。 如果想撤销的话就只能不压缩路径，但是这样复杂度是 O(n^2) 的，显然会TLE啊。

这时候我们可以使用按秩合并的思想。 按秩合并顾名思义就是按照一定的秩序进行合并。

我们一般有两种选择：1. 按照深度合并 2. 按照大小合并。 我一般喜欢用按照大小合并的方法（更高端的名字叫做启发式合并），因为这样比较简单。 下面放代码：

inline int get(int x) {
    return x == fa[x] ? x : get(fa[x]);
}
inline void merge(register int x, register int y) {
    int fx = get(x), fy = get(y);
    if(size[fx] > size[fy]) swap(fx, fy);
    sta[++top] = (Stack){fx, fy, size[fx]};
    fa[fx] = fy, size[fy] += size[fx], size[fx] = 0;
}

前置知识2：线段树分治

线段树分治就是把离线的分治算法和线段树和在了一起。 我们都知道分治是可以降低时间复杂度的，而线段树支持区间的修改和查询操作。 那么把这两者和在一起大概就类似与线段树分治，（说的比较片面，但是我只是想形象亿点点）。

实际上线段树分治很难讲清楚，所以就那这道题来说吧。

题目分析

对于这道题我们可以以时间（询问）为轴建线段树，这样就可以在时间区间上加入一条边。

然后我们离线进行查询。

对线段树进行一个dfs，向下递归的时候加入边，回溯的时候删边就可以解决这个问题。

对于如何用并查集判断是否为二分图：

我们可以将一个点拆为两个点，类似于网络流中的点化边。

然后如果这两个点连通就说明不合法。

代码时刻

#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int N = 1e5 + 5;
inline int read(int s = 0, char ch = getchar()) {
    while(!isdigit(ch)) { ch = getchar(); }
    while(isdigit(ch)) { s = s*10 + ch - '0'; ch = getchar(); }
    return s;
}
vector <int> tr[N<<2];
int n, m, k, fa[N<<1], size[N<<1], top;
struct edge { int from, to; } e[N<<1];
struct Stack { int x, y, w; } sta[N<<2];
inline void modify(int rt, int l, int r, int s, int t, int w) {
    if(s > t) return;
    if(s <= l && r <= t) { tr[rt].push_back(w); return; }
    int mid = (l + r) / 2; 
    if(s <= mid) modify(lson, l, mid, s, t, w);
    if(t > mid) modify(rson, mid + 1, r, s, t, w);
}
inline int get(int x) {
    return x == fa[x] ? x : get(fa[x]);
}
inline void merge(register int x, register int y) {
    int fx = get(x), fy = get(y);
    if(size[fx] > size[fy]) swap(fx, fy);
    sta[++top] = (Stack){fx, fy, size[fx]};
    fa[fx] = fy, size[fy] += size[fx], size[fx] = 0;
}
void solve(int rt, int l, int r) {//关键部分
    int flag = 1, lasttop = top;
    for(register int i = 0; i < tr[rt].size(); ++i) {
        int from = e[tr[rt][i]].from, to = e[tr[rt][i]].to;
        int fa = get(from), fb = get(to);
        if(fa == fb) {//不合法
            for(register int j = l; j <= r; ++j) puts("No");
            flag = 0; break;
        }
        merge(from, to + n), merge(from + n, to);//合并
    }
    if(flag == 1) {
        if(l == r) puts("Yes");
        else {
            int mid = (l + r) / 2;
            solve(lson, l, mid), solve(rson, mid + 1, r);
        }
    }
    while(top > lasttop) {//删边，复原
        size[sta[top].y] -= sta[top].w;
        fa[sta[top].x] = sta[top].x;
        size[sta[top].x] += sta[top].w;
        top--;
    }
}
int main() {
    n = read(), m = read(), k = read();
    for(register int i = 1, l, r; i <= m; ++i) {
        e[i].from = read(), e[i].to = read();
        l = read() + 1, r = read();
        modify(1, 1, k, l, r, i);
    }
    for(register int i = 1; i <= n * 2; ++i) fa[i] = i, size[i] = 1;//并查集初始化
    solve(1, 1, k);
    return 0;
}