线段树分治

线段树分治可以解决这样的问题：

1. 对于一些操作，每个操作只在 \(l\) ~ \(r\) 的的时间内有效。
2. 对于一些操作，询问某个时间点所有操作的贡献。

经典 例题

算法思路

对于这道题，因为二分图的充要条件是 不存在奇环，所以可以使用 扩展域并查集 解决。
我们考虑离线优化：对于每个时间点建立一颗线段树，把操作挂到线段树上。我们使用样例模拟一下：

我们对时间向右偏移一位：[0,3] 对应 [1,4]。但是 4 是消失的时间，所以存在的时间为 [1,3]。

上图为挂在线段树上的操作。

1. 计算答案时，从根节点出发， 每到一个节点，将挂在这个节点上的所有边合并，然后递归处理左右儿子。如果发现某条边合并后会出现奇环，就输出 No。
2. 当到达叶子节点时，如果合并了所有挂在当前节点上的边，依旧满足二分图的性质，就输出 Yes。
3. 回溯时，由于并查集不支持删边，所以可以使用可撤销并查集（也就是用一个栈记录一下所有对并查集的操作）。因为它可撤销，所以不能路径压缩，为了保持算法时间上的正确性，要使用按秩合并。

#include<bits/stdc++.h>
using namespace std;
const int N = 10101010;
int read(){
	int x = 0,f = 0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}

int n,m,k,fa[N],height[N],top;
struct E{int x,y;}e[N];
struct Stack{int x,y,add;}st[N];
vector<int> t[N];

int findfa(int x)
{
	while(x != fa[x]) x = fa[x];
	return fa[x];
}
void debug()
{
	printf("\n****************\n下标");
	for(int i = 1;i <= n*2;i++) printf("%d ",i); 
	printf("\n父亲");
	for(int i = 1;i <= n*2;i++) printf("%d ",fa[i]);
	printf("\n祖先(代表元)");
	for(int i = 1;i <= n*2;i++) printf("%d ",findfa(i));
}
void merge(int x,int y)
{
	int fx = findfa(x),fy = findfa(y);
	if(height[fx] > height[fy]) swap(fx,fy); // 按秩合并
	st[++top] = (Stack){fx,fy,height[fx] == height[fy]}; // 用一个栈记录信息
	fa[fx] = fy;
	if(height[fx] == height[fy]) height[fy]++;
}
void update(int u,int l,int r,int L,int R,int x)
{
	if(l > R || r < L) return;
	if(L <= l && r <= R) {t[u].push_back(x);return;}
	int mid = l + r >> 1;
	update(u<<1,l,mid,L,R,x);
	update(u<<1|1,mid+1,r,L,R,x);
}
void solve(int u,int l,int r)
{
//	debug();
	int ans = 1; // 是不是二分图
	int lasttop = top;
	// 如果当前区间有时间线，若没有环就合并，有环就输出
	for(int i = 0;i < t[u].size();i++)
	{
		int a = findfa(e[t[u].at(i)].x);
		int b = findfa(e[t[u].at(i)].y);
		if(a == b)
		{
			for(int k = l;k <= r;k++)
			printf("No\n");
			ans = 0;
			break;
		}
		merge(e[t[u].at(i)].x,e[t[u].at(i)].y+n);
		merge(e[t[u].at(i)].y,e[t[u].at(i)].x+n);
	}
	if(ans) // 如果是二分图，就继续遍历儿子
	{
		if(l==r) printf("Yes\n");
		else 
		{
			int mid = l+r>>1;
			solve(u<<1,l,mid);
			solve(u<<1|1,mid+1,r);
		}
	}
	// 回溯，如果当前区间做过合并操作，就逐个撤销
	while(top > lasttop)
	{
		height[fa[st[top].x]] -= st[top].add;
		fa[st[top].x] = st[top].x;
		top--;
	}
	return;
}
int main()
{
	n = read();m = read();k = read();
	for(int i = 1;i <= m;i++)
	{
		e[i].x = read();e[i].y = read();
		int l = read()+1,r = read();
		update(1,1,k,l,r,i);
	}
	for(int i = 1;i <= 2*n;i++) fa[i] = i,height[i] = 1;
	solve(1,1,k);
	return 0;
}