rt，这题不能路径压缩，但是我懒得写按size合并了，于是我写了一个随机合并：

• 给每个节点rand一个随机值rnd
• 合并的时候把rnd较小的点当父亲

一交过了，我还以为数据水了，把随机化的删掉，结果就过不了hack数据了。我自己还试着hack了一会，似乎卡不掉。

这样的合并方式能不能卡掉呀？复杂度是否是一个log呀？谢谢

代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define vec vector
using namespace std;
using pi=pair<int,int>;
mt19937 myrand(65536);

int n,m,k;
vec<int> fa,rnd;
stack<pi> hist;
int find(int x){return fa[x]==x?x:find(fa[x]);}
void mrg(int x,int y){
	x=find(x),y=find(y);
	if(rnd[x]>rnd[y])swap(x,y);
	hist.push({y,fa[y]});
	fa[y]=x;
}


bool link(int x,int y){
	mrg(x,y+n);
	mrg(x+n,y);
	return find(x)!=find(x+n);
}
void undo(){
	pi x=hist.top();hist.pop();
	fa[x.fi]=x.se;
}




vec<vec<pi>> t;
#define ls p<<1
#define rs p<<1|1
void mod(int p,int l,int r,int ml,int mr,pi mv){
	if(mr<l || r<ml)return;
	if(ml<=l && r<=mr){
	//if(ml==2 && mr==3)cerr<<l<<" "<<r<<"!!!"<<endl;
		t[p].push_back(mv);
		return;
	}
	int mid=(l+r)>>1;
	mod(ls,l,mid,ml,mr,mv);
	mod(rs,mid+1,r,ml,mr,mv);
}

void que(int p,int l,int r,bool last){
	bool cur=last;
	int csz=hist.size();
	for(pi &x:t[p])
		if(!(cur&=link(x.fi,x.se)))
			break;
	if(l<r){
		int mid=(l+r)>>1;
		que(ls,l,mid,cur);
		que(rs,mid+1,r,cur);
	}
	else cout<<(cur?"Yes\n":"No\n");
	while(hist.size()>csz)undo();
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;

	fa.resize(n*2+1);
	rnd.resize(n*2+1);
	for(int i=1;i<=n*2;i++)
		fa[i]=i,rnd[i]=myrand();

	t.resize(k*4+5);

	while(m--){
		int u,v,l,r;
		cin>>u>>v>>l>>r;
		mod(1,1,k,l+1,r,{u,v});
	}
	que(1,1,k,1);
	return 0;
}