BZOJ-5005: 乒乓游戏

Description

对于两个区间，如果(a,b)和(c,d)区间满足 c< a < d 或者 c < b < d，就可以从(a,b)到(c,d)去。现在有以下两种操作：
1 x y：(x < y)表示在区间集合中添加(x,y)这个区间，保证新加入的区间长度一定比之前的所有区间长度长；
2 a b：(a ≠ b)表示询问是否有一条路从第 a 个区间到第 b 个区间。
游戏开始前，区间集合为空。现在，请你来回答所有的询问。n<=10^5 else<=10^9

我在一个考试中把这道题拿出来了，结果知道这道题的人都以为码长巨大，不去写了。。。实际上，代码并不难，想法到是有点
发现如果有a< b < c < d，等价于区间(a,c)和(b,d)相互可达，等价于(b,c)可以单向到达(a,d)。
由于区间长度严格递增，之前的区间不可能包含当前区间，所以要么自己一个不能到达任何区间，要么和之前的一些区间互相可达，所以有包含其端点的区间既可以互相可达，并不可能存在包含当前区间的区间。
尝试利用这个性质，将互相可达的区间看成一个整体，考虑贡献：
对于新加入的区间，我们需要统计这个整体的最小的l，以及最大的r，看是否可以和新加入的区间形成一个整体。
对于查询操作：1.所属于一个整体，可达。 2.所属于两个整体，那么两个整体一定没有交，不然就会变成一个整体。那么其可达当且仅当a区间是b区间的子区间，即整体的并集互相包含。
综上，对于互相可达的区间，我们可以将其合并为一个区间，大小为所有区间的并集。

那么解法就简单了。
用并查集维护区间所属整体的关系，对于每个整体维护其并集(li,ri)
对于新加入区间操作，需要统计包含l,r的区间是谁。
用线段树将之前所有的区间差成log段，用链表挂在上面，对l,r经过的节点上挂的区间进行合并。处理出新的并集(li,ri)，再差成log段挂到到线段树中。对于已经合并没的整体，打标记删除，表示当前的整体已经被合并，在链表上扫到的时候再删除。
对于查询操作，直接拿出来整体的并集(li,ri)判断。
由于每个区间只拆成了log段，每段至多删除一次，每个区间至多合并一次。复杂度O(nlogn) 空间nlogn

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
int n,id,fa[N],L[N],R[N],sw[N],q1[N],q2[N],b[N<<2],c[N<<2],tot;
int find(int x){return x==fa[x] ? x:fa[x]=find(fa[x]);}
bool del[N];
int head[N<<4],to[N*40],nxt[N*40],cnt;
inline void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
void merge(int p,int l,int r,int x)
{
    while(head[p])
    {
        int x=to[head[p]];
        head[p]=nxt[head[p]];
        if(!del[x])
        {
            del[x]=1,fa[x]=id;
            L[id]=min(L[id],L[x]);
            R[id]=max(R[id],R[x]);
        }
    }
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) merge(p<<1,l,mid,x);
    else merge(p<<1|1,mid+1,r,x);
}
void fix(int p,int l,int r,int x,int y)
{
    if(x<=l&&y>=r) {add(p,id); return ;}
    int mid=(l+r)>>1;
    if(x<=mid) fix(p<<1,l,mid,x,y);
    if(y>mid) fix(p<<1|1,mid+1,r,x,y);
}
int getid(int x) {return lower_bound(c+1,c+tot+1,x)-c;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",sw+i,q1+i,q2+i);
        if(sw[i]==1)
        {
            b[++cnt]=q1[i]; b[++cnt]=q2[i];
            b[++cnt]=q1[i]+1; b[++cnt]=q2[i]-1;
        }
    }
    sort(b+1,b+cnt+1); c[++tot]=b[1];
    for(int i=2;i<=cnt;++i) if(b[i]!=c[tot]) c[++tot]=b[i];
    int x,y;
    for(int i=1;i<=n;++i)
    {
        if(sw[i]==1) x=getid(q1[i]),y=getid(q2[i]);
        else x=q1[i],y=q2[i];
        if(sw[i]==1)
        {
            ++id; L[id]=x; R[id]=y;
            merge(1,1,tot,x);
            merge(1,1,tot,y);
            fix(1,1,tot,L[id]+1,R[id]-1);
        }
        else
        {
            y=find(y);
            if(find(x)==y||(L[x]>L[y]&&L[x]<R[y])||(R[x]>L[y]&&R[x]<R[y])) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}