正题

题目链接:https://www.luogu.com.cn/problem/CF319E

题目大意

定义一个区间 \((a,b)\) 能走到另一个区间 \((c,d)\) 当 \(c<a<d,c<b<d\) 。

你有两个操作

1. 往集合中加入一个区间 \((a,b)\) ，保证加入的区间长度单调递增。
2. 询问一个区间能否走到另一个区间。

\(1\leq n\leq 10^5,1\leq a\leq b\leq 10^9\)

解题思路

我们考虑假设我们从一个区间 \(x\) 能走到区间 \(y\) ，区间 \(y\) 能走到区间 \(z\) ，那么区间 \(x\) 肯定能走到区间 \(z\) 。也就是对于单向边我们只会走一次，分析一下性质，如果我们知道区间 \(b\) 所在的边双连通分量范围 \([L,R]\) ，那么区间 \(a\) 能走到区间 \(b\) 的充要条件是区间 \(a\) 是 \([L,R]\) 的一个严格子区间。

那么现在问题就变为了动态维护这些区间的边双了，因为保证了加入的区间长度单调递增，所以我们不需要考虑新加入的区间被包含的可能，所以如果新加入的区间与某个边双的范围区间 \([L,R]\) 是双向的，这个区间又不会被这个边双包含，所以这个区间肯定能并入这个边双里。

我们用线段树维护对于每个以 \(x\) 位置为左端点的边双，右端点的最大值，这样就可以暴力每次从线段树中取出一个边双看与新区间是否连通，使用并查集合并即可。

时间复杂度：\(O(n\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=2e5+10;
int n,m,cnt,op[N],x[N],y[N],b[N],fa[N],pos[N],l[N],r[N];
pair<int,int> w[N<<2];
set<pair<int,int> >v[N];
void Change(int x,int L,int R,int pos,pair<int,int> val){
	if(L==R){
		w[x]=max(w[x],val);
		v[L].insert(val);
		return;
	}
	int mid=(L+R)>>1;
	if(pos<=mid)Change(x*2,L,mid,pos,val);
	else Change(x*2+1,mid+1,R,pos,val);
	w[x]=max(w[x*2],w[x*2+1]);
	return;
}
bool Del(int x,int L,int R,int l,int r,pair<int,int> val){
	if(l>r)return 0;
	if(L==R){
		if(w[x]!=val)return 0;
		v[L].erase(val);
		if(v[L].size())w[x]=*v[L].rbegin();
		else w[x]=mp(0,0);
		return 1;
	}
	int mid=(L+R)>>1,flag=0;
	if(L==l&&R==r){
		if(w[x]!=val)flag=0;
		else if(w[x*2]==val)flag=Del(x*2,L,mid,l,mid,val);
		else flag=Del(x*2+1,mid+1,R,mid+1,r,val);
	}
	else{
		if(r<=mid)flag=Del(x*2,L,mid,l,r,val);
		else if(l>mid)flag=Del(x*2+1,mid+1,R,l,r,val);
		else{
			bool flag=Del(x*2,L,mid,l,mid,val);
			if(!flag)flag=Del(x*2+1,mid+1,R,mid+1,r,val);
		}
	}
	w[x]=max(w[x*2],w[x*2+1]);
	return flag;
}
pair<int,int> Ask(int x,int L,int R,int l,int r){
	if(l>r)return mp(0,0);
	if(L==l&&R==r)return w[x];
	int mid=(L+R)>>1;
	if(r<=mid)return Ask(x*2,L,mid,l,r);
	if(l>mid)return Ask(x*2+1,mid+1,R,l,r);
	return max(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));
}
int find(int x)
{return (fa[x]==x)?(x):(fa[x]=find(fa[x]));}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&op[i],&x[i],&y[i]);
		if(op[i]==1){
			b[++m]=x[i];
			b[++m]=y[i];
		}
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(b+1,b+1+m);
	m=unique(b+1,b+1+m)-b-1;
	for(int i=1;i<=n;i++){
		if(op[i]==1){
			cnt++;pos[cnt]=i;
			x[i]=lower_bound(b+1,b+1+m,x[i])-b;
			y[i]=lower_bound(b+1,b+1+m,y[i])-b;
			l[cnt]=x[i];r[cnt]=y[i];
			while(true){
				pair<int,int> son=Ask(1,1,m,x[i],y[i]-1);
				if(son.first<=y[i])break;
				int z=son.second;
				Del(1,1,m,x[i],y[i]-1,son);
				if(fa[z]!=z)continue;
				fa[z]=cnt;
				l[cnt]=min(l[cnt],l[z]);
				r[cnt]=max(r[cnt],r[z]);
			}
			while(true){
				pair<int,int> son=Ask(1,1,m,1,x[i]-1);
				if(son.first<=x[i])break;
				int z=son.second;
				Del(1,1,m,1,x[i],son);
				if(fa[z]!=z)continue;
				fa[z]=cnt;
				l[cnt]=min(l[cnt],l[z]);
				r[cnt]=max(r[cnt],r[z]);
			}
			Change(1,1,m,l[cnt],mp(r[cnt],cnt));
		}else{
			if(find(x[i])==find(y[i]))puts("YES");
			else{
				x[i]=pos[x[i]];y[i]=find(y[i]);
				if(x[x[i]]>=l[y[i]]&&y[x[i]]<=r[y[i]]&&!(x[x[i]]==l[y[i]]&&y[x[i]]==r[y[i]]))
					puts("YES");
				else puts("NO");
			}
		}
	}
	return 0;
}