本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 21:36:59

就是对于所有前缀查询，可以把操作序列放在线段树上进行维护，每一个操作序列都对应log个区间，对于每一个区间暴力放进去与拿出来。

模板的代码

const int N=2e5+5;

int n;

struct DSU{
	int fa[N<<1],sum[N<<1];
	struct hhh{
		int u,v;
		bool tag;
	}stk[N];int hd;
	void init(){
		for(int i=1;i<=2*n;i++)
			fa[i]=i,sum[i]=1;
	}
	int fd(int x){
		return fa[x]==x?x:fd(fa[x]);
	}
	void merge(int x,int y){
		int fx=fd(x),fy=fd(y);
		if(fx!=fy){
			fx=fd(x+n);
			if(sum[fx]<sum[fy])
				swap(fx,fy);
			hd++;
			stk[hd]={fx,fy,stk[hd-1].tag};
			sum[fx]+=sum[fy];
			fa[fy]=fx;
			fx=fd(x);
			fy=fd(y+n);
			if(sum[fx]<sum[fy])
				swap(fx,fy);
			hd++;
			stk[hd]={fx,fy,stk[hd-1].tag};
			sum[fx]+=sum[fy];
			fa[fy]=fx;
		}else
			stk[++hd]={0,0,1},stk[++hd]={0,0,1};
	}
	void del(){
		sum[stk[hd].u]-=sum[stk[hd].v];
		fa[stk[hd].v]=stk[hd].v;
		hd--;
		sum[stk[hd].u]-=sum[stk[hd].v];
		fa[stk[hd].v]=stk[hd].v;
		hd--;
	}
}D;

struct Seg_Tree{
	vector<pir>v[N<<2];
	void update(int x,int l,int r,int L,int R,pir a){
		if(L<=l&&r<=R)
			v[x].pb(a);
		else{
			if(L<=mid)
				update(ls,l,mid,L,R,a);
			if(R>mid)
				update(rs,mid+1,r,L,R,a);
		}
	}
	void calc(int x,int l,int r){
		for(pir i:v[x])
			D.merge(i.fi,i.se);
		if(l==r)
			printf(D.stk[D.hd].tag?"No\n":"Yes\n");
		else{
			calc(ls,l,mid);
			calc(rs,mid+1,r);
		}
		int tmp=v[x].size();
		while(tmp--)
			D.del();
	}
}T;

signed main(){
	n=read();int m=read(),k=read();
	D.init();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),l=read()+1,r=read();
		T.update(1,1,k,l,r,{u,v});
	}
	T.calc(1,1,n);
	return 0;
}