#C240915D. 神奇的区间
标签（Label）
- 线段树
- 并查集
- 观察+分析
- 离散化
网址（Website）
题解（Solution）
$\qquad$容易观察得到当两个区间相交但不包含时，二者可以互相到达，我们可以直接将这两个区间合并为一个；如果两个区间是包含关系，那么便只能从小的区间通往大的区间；否则，两个区间不相交，没有连边。于是，我们很容易就会发现，不可互达的区间连边是一个森林的结构。考虑使用并查集来维护合并这个过程。
$\qquad$合并之后，两个区间要么就在同一个并查集中，此时彼此之间可以互达；如果不在一个并查集中，只需要看二者的祖先能否有连边即可。注意，此处的并查集合并时要把祖先更新，保证区间长度最长（即将 $[a,b]$ 和 $[c,d]$ 合并为 $[min(a,c),max(b,d)]$ ），这样在判断能第二种情况时才能保证正确性。
$\qquad$时间复杂度 $O(nlogn)$ 。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;
int op[N],st[N],ed[N],rk[N];
int lx[N],rx[N];
int n,cnt,num;
int fa[N];inline int find(int x){
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
vector<int> cur[N<<2|3];
inline void update(int p,int l,int r,int pos){
for(auto x:cur[p]){//合并区间
lx[num] = min(lx[num], lx[x]);
rx[num] = max(rx[num], rx[x]);
fa[find(x)] = num;
}cur[p].clear();
if(l>=r) return;
if(pos<=mid) update(ls,l,mid,pos);
else update(rs,mid+1,r,pos);
}
inline void add_edge(int p,int l,int r,int L,int R){
if(L<=l && r<=R) return cur[p].emplace_back(num),void();
if(L<=mid) add_edge(ls,l,mid,L,R);
if(R>mid) add_edge(rs,mid+1,r,L,R);
}
inline void add(int l,int r){
update(1,1,cnt,l), update(1,1,cnt,r);
//所有在二者之间的部分都可以合并到这个区间
if(lx[num] + 1 < rx[num]) add_edge(1, 1, cnt, lx[num]+1, rx[num]-1);
}
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
cin>>n;int Tim = clock();
For(i,1,n){
cin>>op[i]>>st[i]>>ed[i];
if(op[i]==1) rk[++cnt] = st[i], rk[++cnt] = ed[i];
}
sort(rk+1,rk+cnt+1);
cnt = unique(rk+1,rk+cnt+1)-rk-1;
For(i,1,n){
if(op[i]==1){
++num;fa[num] = num;
st[i] = lower_bound(rk+1,rk+cnt+1,st[i]) - rk;
ed[i] = lower_bound(rk+1,rk+cnt+1,ed[i]) - rk;
lx[num] = st[i], rx[num] = ed[i];//记录这个点作为左区间和右区间所在的位置
add(st[i],ed[i]);//加入
}else{
int x = find(st[i]), y = find(ed[i]);
if(x==y) cout<<"YES\n";//如果二者可以互通
else{
if((lx[y]<lx[x] && lx[x]<rx[y]) || (lx[y]<rx[x] && rx[x]<rx[y]))
cout<<"YES\n";
else cout<<"NO\n";
}
}
}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
