线段树分治学习笔记附加可撤销并查集
longdie
2020-12-31 14:45:55
额， 我又来写学习笔记了。
首先放个题目链接得勒。
[可恶的题目](https://www.luogu.com.cn/problem/P5787)
## 前置知识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;
}
```