# 问题引入

给一些操作，只在 $l \sim r$ 时间段内有效。
给一些询问，查询在某一时间内所有操作的贡献。

# 主要思想

我们可以把操作和询问都离线下来，然后对于时间轴建一棵线段树。

对于操作，相当于是在线段树上进行区间修改；对于查询，不停地向下递归，统计答案，回溯时撤销掉操作。

这样的思想被称之为线段树分治。

# 例题

P5787 二分图 /【模板】线段树分治

# Solution

出现二分图的条件是不存在奇环，可以使用扩展域并查集维护。

再来看如何建树，我们先按照时间轴分区间，然后对于每个点开一个 vector ，对于每个操作所在的区间，往线段树上对应的节点的 vector 里连边即可。

询问时，把左右儿子合并一下，并向下递归，如果到了儿子时都没有出现奇环，那么输出 Yes 。

回溯时，我们要进行撤销操作，所以要使用可撤销并查集，简单来说，就是开个栈记录并查集每一次合并时都干了什么，并且不能再路径压缩。

# Code

mark

	#include <bits/stdc++.h>
	#define ls(x) x << 1
	#define rs(x) x << 1 \| 1

	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;
	}

# End

分治线段树