www.lydsy.com/JudgeOnline/upload/task.pdf
第一题题意可以转为选一个长度k的序列，每一项二进制的1的位置被下一项包含，且总和为1，考虑每个二进制位的出现位置，可以转化为一个多重背包求方案数的问题。
第二题构成一些环，可以每个环直接计算，然后合并答案。
第三题区间包含相当于单向边，区间相交不包含就是双向边，将区间相交不包含的情况缩点，剩余的单向边构成一棵树（几个被缩起来的区间可以用它们的并集表示），用lct维护树形态，查询即为询问两点是否是祖先关系，对于修改，由于区间长度递增，只有至多两种缩点情况：1.新加入的区间与某棵树的根缩点（另用平衡树维护所有根对应的区间，实际上需要再分几类）；2.新加入的区间与树上非根的点缩点（另用线段树维护所有非根节点对应的区间）。
前两题代码实现比较简单，所以这里只给出第三题的代码。
#include<bits/stdc++.h> int _(){ int x=0,f=1,c=getchar(); while(c<48)c=='-'?f=-1:0,c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x*f; } #define lc ch][0 #define rc ch][1 #define fa ch][2 const int N=2e5+77,inf=0x3f3f3f3f; struct itv{ int l,r,id; bool operator<(const itv&w)const{return l<w.l;} }; struct cmpl{bool operator()(const itv&a,const itv&b){return a.l>b.l;}}; struct cmpr{bool operator()(const itv&a,const itv&b){return a.r<b.r;}}; std::set<itv>st; int n,f[N],ch[N][4],idp=0; int qs[N][3],xs[N],xp=0,mx=1,tl[577777],tr[577777]; std::priority_queue<itv,std::vector<itv>,cmpl>ls[N]; std::priority_queue<itv,std::vector<itv>,cmpr>rs[N]; int gf(int x){ while(x!=x[f])x=x[f]=x[f][f]; return x; } bool nrt(int x){return x==x[fa][lc]||x==x[fa][rc];} int wc(int x){return x==x[fa][rc];} void rot(int x){ int f=x[fa],g=f[fa],d=wc(x); if(nrt(f))g[ch][wc(f)]=x; x[fa]=g; (f[ch][d]=x[ch][d^1])[fa]=f; (x[ch][d^1]=f)[fa]=x; } void sp(int x){ while(nrt(x)){ int f=x[fa]; if(nrt(f))rot(wc(x)==wc(f)?f:x); rot(x); } } int acs(int x){int y=0;for(;x;sp(x),x[rc]=y,y=x,x=x[fa]);return y;} void lk(int a,int b){acs(a)[fa]=b;} void ctlk(int a,int b){acs(a),sp(a);a[lc][fa]=0,a[lc]=0,a[fa]=b;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} void tl_up(int x){ tl[x+mx]=ls[x].size()?ls[x].top().l:inf; for(x=x+mx>>1;x;x>>=1)tl[x]=min(tl[x<<1],tl[(x<<1)+1]); } void tr_up(int x){ tr[x+mx]=rs[x].size()?rs[x].top().r:-inf; for(x=x+mx>>1;x;x>>=1)tr[x]=max(tr[x<<1],tr[(x<<1)+1]); } int $(int x){ return std::lower_bound(xs+1,xs+xp+1,x)-xs; } void tr_ins(itv w){ int _l=$(w.l),_r=$(w.r); ls[_r].push(w),tl_up(_r); rs[_l].push(w),tr_up(_l); } void chk(itv w,int z){ int p,u; while(tl[z]<w.l){ for(p=z;p<mx;p<<=1,p+=tl[p]>=w.l); p-=mx; u=ls[p].top().id; if(u==f[u])ctlk(u,f[u]=w.id); ls[p].pop(); tl_up(p); } while(tr[z]>w.r){ for(p=z;p<mx;p<<=1,p+=tr[p]<=w.r); p-=mx; u=rs[p].top().id; if(u==f[u])ctlk(u,f[u]=w.id); rs[p].pop(); tr_up(p); } } void tr_del(itv w){ for(int l=$(w.l)+mx,r=$(w.r)+mx;r-l>1;l>>=1,r>>=1){ if(~l&1)chk(w,l+1); if(r&1)chk(w,r-1); } } void ins(itv w){ tr_del(w); std::set<itv>::iterator it=st.lower_bound(w); if(it!=st.end()&&it->l==w.l&&it->r>w.r)return lk(w.id,f[w.id]=it->id); if(it!=st.begin()&&(--it)->r>w.l){ int u=it->id; if(it->r>=w.r)return lk(w.id,f[w.id]=u); w.l=it->l,f[u]=w.id; lk(u,w.id); st.erase(it); } while((it=st.lower_bound(w))!=st.end()&&it->l<w.r){ int u=it->id; if(it->r>w.r)w.r=it->r,f[u]=w.id; else tr_ins(*it); lk(u,w.id); st.erase(it); } st.insert(w); } bool query(int x,int y){ x=gf(x),y=gf(y); if(x==y)return 1; x=acs(x); int y0=y; for(;nrt(y);y=y[fa]); sp(y0); return x==y; } int main(){ n=_(); for(int i=1;i<=n;++i){ qs[i][0]=_(); qs[i][1]=_(); qs[i][2]=_(); if(qs[i][0]==1)xs[++xp]=qs[i][1],xs[++xp]=qs[i][2]; } std::sort(xs+1,xs+xp+1); for(;mx<=xp+5;mx<<=1); for(int i=mx*2-1;i;--i)tl[i]=inf,tr[i]=-inf; for(int i=1;i<=n;++i){ f[i]=i; int o=qs[i][0],x=qs[i][1],y=qs[i][2]; if(o==1)ins((itv){x,y,++idp}); else puts(query(x,y)?"YES":"NO"); } return 0; }