要求支持操作（次数10^5）：
1、插入一个区间[x,y]，保证比之前所有区间都长
2、询问第a个区间能否走到第b个区间
[a,b]能走到[c,d]=>c<a<d或c<b<d
考虑[a,b]能走到的所有区间是 从端点开始类似dfs走到的所有区间的并，显然这个并也是一个区间。
我们考虑维护这个东西。用并查集维护区间的联通块（块内区间能互相到达），记下最左和最右
我们考虑所有严格包含点a的区间，他们都是能与[a,b]合并的，找这个可以用线段树维护
SGT上每个节点[x,y]开一个vet记下所有当前完整覆盖这个[x,y]的所有区间，查询时暴力扫
每次我们[a,b]先合并完 然后[a,b]扩展到了[a',b']，我们将其插到SGT中
对于SGT上那些旧的区间 我们不用立即删掉 在我们查询的时候判断一下当前这个区间是否被合并了即可
询问时我们考虑哪些区间能走到[a,b]
我们考虑[a,b]所在联通块的左右[a',b']，如果一个区间[c,d]且a'<c<d<b'，那么[c,d]能走到[a',b']，因为他们在同一个联通块中。（注意如果a'=c<d=b'是不行的。）
复杂度？每次插入覆盖logn个节点，由于题目中条件“比之前所有区间都长”所以合并时的复杂度是可以保证的。查询是O(1)的。总的好像是O(nlogn）。
#include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<vector> #include<map> #include<queue> #include<string> #include<bitset> #include<iomanip> #include<iostream> #include<cmath> using namespace std; #define rep(i,x,y) for(i=x;i<=y;i++) #define _rep(i,x,y) for(i=x;i>=y;i--) #define CL(S,x) memset(S,x,sizeof(S)) #define CP(S1,S2) memcpy(S1,S2,sizeof(S2)) #define ALL(x,S) for(x=S.begin();x!=S.end();x++) #define sqr(x) ((x)*(x)) #define mp make_pair #define fi first #define se second #define upmin(x,y) x=min(x,y) #define upmax(x,y) x=max(x,y) #define pb push_back #define COUT(S,x) cout<<fixed<<setprecision(x)<<S<<endl typedef long long ll; typedef long double ld; typedef pair<int,int> pii; int read(int&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;return x;} inline char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;} const int N=100010; int m,g,i,j,k,l,p,id; int DQ[N],V[N<<1]; int numV(int x){return lower_bound(V+1,V+1+V[0],x)-V;} struct ask { int id,t,l,r; void input(int i){read(t);if(t==1){V[++V[0]]=read(l);V[++V[0]]=read(r);id=++g;DQ[id]=i;}else read(l),read(r);} }Q[N]; struct UnionSet { int f[N],l[N],r[N]; void init(){int i;rep(i,1,g)f[i]=i;} int get(int x){return f[x]==x?x:f[x]=get(f[x]);} void Union(int x,int y){f[x]=y;upmin(l[y],l[x]);upmax(r[y],r[x]);} void merge(int x,int y){x=get(x);y=get(y);Union(x,y);} }U; struct SGT { vector<int> T[N<<2]; void ins(int i,int x,int y,int l,int r) { if(y<l||x>r)return; if(x>=l&&y<=r){T[i].pb(id);return;} ins(i*2,x,(x+y)/2,l,r); ins(i*2+1,(x+y)/2+1,y,l,r); } #define del(A,i) swap(A[i],A.back()),A.pop_back(),--i void ext(int i,int x,int y,int d) { for(int t=0;t<T[i].size();t++) { int p=U.get(T[i][t]); if(p!=T[i][t])del(T[i],t); else if(U.l[p]<d&&d<U.r[p])U.merge(p,id),del(T[i],t); } if(x!=y)if(d<=(x+y)/2)ext(i*2,x,(x+y)/2,d);else ext(i*2+1,(x+y)/2+1,y,d); } void add(int now) { id=now;int a=U.l[now],b=U.r[now]; ext(1,1,V[0],a); ext(1,1,V[0],b); a=U.l[now];b=U.r[now]; ins(1,1,V[0],a,b); } }T; void work() { int p,l,r; rep(p,1,m) { if(Q[p].t==1) { U.l[Q[p].id]=Q[p].l=numV(Q[p].l); U.r[Q[p].id]=Q[p].r=numV(Q[p].r); T.add(Q[p].id); } else { l=DQ[Q[p].l];r=U.get(Q[p].r); if(U.l[r]<=Q[l].l&&Q[l].r<=U.r[r])printf("YES ");else printf("NO "); } } } int main() { //freopen("1.in","r",stdin);freopen("1.out","w",stdout); int i,j; read(m);rep(i,1,m)Q[i].input(i);U.init(); sort(V+1,V+1+V[0]);j=1;rep(i,2,V[0])if(V[i]!=V[i-1])V[++j]=V[i];V[0]=j; work(); scanf(" "); return 0; }