# 问题引入
-
给一些操作，只在 时间段内有效。
-
给一些询问，查询在某一时间内所有操作的贡献。
# 主要思想
我们可以把操作和询问都离线下来，然后对于时间轴建一棵线段树。
对于操作，相当于是在线段树上进行区间修改；对于查询，不停地向下递归，统计答案，回溯时撤销掉操作。
这样的思想被称之为线段树分治。
# 例题
P5787 二分图 /【模板】线段树分治
# Solution
出现二分图的条件是不存在奇环，可以使用扩展域并查集维护。
再来看如何建树，我们先按照时间轴分区间，然后对于每个点开一个 vector，对于每个操作所在的区间，往线段树上对应的节点的 vector 里连边即可。
询问时，把左右儿子合并一下，并向下递归，如果到了儿子时都没有出现奇环，那么输出 Yes。
回溯时，我们要进行撤销操作，所以要使用可撤销并查集，简单来说，就是开个栈记录并查集每一次合并时都干了什么，并且不能再路径压缩。
# Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
using namespace std;
namespace IO{
inline int read(){
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 1e7 + 10;
int n, m, k;
struct edge{
int x, y;
}e[N];
struct Stack{
int x, y, add;
}stk[N];
int top;
vector <int> g[N];
int f[N], dep[N];
inline int find(int x){
return f[x] == x ? x : find(f[x]);
}
inline void merge(int x, int y){
int fx = find(x), fy = find(y);
if(dep[fx] > dep[fy]) swap(fx, fy);
stk[++top] = (Stack){fx, fy, dep[fx] == dep[fy]};
f[fx] = fy;
if(dep[fx] == dep[fy]) dep[fy]++;
}
inline void update(int L, int R, int x, int l, int r, int rt){
if(l > R || r < L) return;
if(L <= l && r <= R) return g[rt].push_back(x), void();
int mid = (l + r) >> 1;
update(L, R, x, l, mid, ls(rt)), update(L, R, x, mid + 1, r, rs(rt));
}
inline void Delete(int lst){
while(top > lst){
dep[f[stk[top].x]] -= stk[top].add;
f[stk[top].x] = stk[top].x;
top--;
}
}
inline void solve(int l, int r, int u){
int flag = 1, lst = top;
for(auto v : g[u]){
int fx = find(e[v].x), fy = find(e[v].y);
if(fx == fy){
for(int i = l; i <= r; ++i) puts("No");
flag = 0;
break;
}
merge(e[v].x, e[v].y + n);
merge(e[v].y, e[v].x + n);
}
if(flag){
if(l == r) puts("Yes");
else{
int mid = (l + r) >> 1;
solve(l, mid, ls(u)), solve(mid + 1, r, rs(u));
}
}
Delete(lst);
}
int main(){
n = read(), m = read(), k = read();
for(int i = 1; i <= m; ++i){
e[i] = (edge){read(), read()};
int l = read() + 1, r = read();
update(l, r, i, 1, k, 1);
}
for(int i = 1; i <= (n << 1); ++i) dep[i] = 1, f[i] = i;
solve(1, k, 1);
return 0;
}
