Luogu4899 IOI2018狼人（kruskal重构树+主席树）

　　可以发现询问的即是“由起点开始‘只经过编号大于等于l的点’所形成的连通块”与“由终点开始‘只经过编号小于等于r的点’所形成的连通块”是否有交集。于是建出重构树，就可以知道每个询问的连通情况了。现在要知道的是两个连通块的交集，考虑每个点是否有可能在里面。于是按照两棵重构树的dfs序给每个点一个二维坐标，问题就变为二维数点了，主席树即可。

　　注意编号从0开始。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 200010

#define M 400010

int n,m,q,root[N<<],cnt;

struct data{int x,y;

}e[M];

struct data2{int l,r,x;

}tree[N<<];

bool cmp(const data&a,const data&b)

{

    return a.y<b.y;

}

struct kruskal_tree

{

    int t,p[N<<],cnt,tot,fa[N<<],value[N<<],dfn[N<<],size[N<<],f[N<<][];

    struct data{int to,nxt;}edge[M<<];

    void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

    void dfs(int k)

    {

        dfn[k]=++tot;

        size[k]=;

        for (int i=p[k];i;i=edge[i].nxt)

        {

            f[edge[i].to][]=k;

            dfs(edge[i].to);

            size[k]+=size[edge[i].to];

        }

    }

    int geta(int x,int k)

    {

        for (int j=;~j;j--) if (value[f[x][j]]>=k) x=f[x][j];

        return x;

    }

    int getb(int x,int k)

    {

        for (int j=;~j;j--) if (value[f[x][j]]<=k) x=f[x][j];

        return x;

    }

    void make()

    {

        for (int i=;i<=n;i++) fa[i]=i,value[i]=i;cnt=n;

        for (int i=;i<=m;i++)

        if (find(e[i].x)!=find(e[i].y))

        {

            int u=find(e[i].x),v=find(e[i].y);

            cnt++;fa[u]=fa[v]=fa[cnt]=cnt;

            addedge(cnt,u),addedge(cnt,v);

            value[cnt]=e[i].y;

        }

        dfs(cnt);

        f[cnt][]=cnt;

        for (int j=;j<;j++)

            for (int i=;i<=cnt;i++)

            f[i][j]=f[f[i][j-]][j-];

    }

}a,b;

void ins(int &k,int l,int r,int x)

{

    tree[++cnt]=tree[k],k=cnt;tree[k].x++;

    if (l==r) return;

    int mid=l+r>>;

    if (x<=mid) ins(tree[k].l,l,mid,x);

    else ins(tree[k].r,mid+,r,x);

}

int query(int x,int y,int l,int r,int p,int q)

{

    if (!x) return ;

    if (l==p&&r==q) return tree[x].x>tree[y].x;

    int mid=l+r>>;

    if (q<=mid) return query(tree[x].l,tree[y].l,l,mid,p,q);

    else if (p>mid) return query(tree[x].r,tree[y].r,mid+,r,p,q);

    else return query(tree[x].l,tree[y].l,l,mid,p,mid)|query(tree[x].r,tree[y].r,mid+,r,mid+,q);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("wolf.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),q=read();

    for (int i=;i<=m;i++)

    {

        e[i].x=read()+,e[i].y=read()+;

        if (e[i].x>e[i].y) swap(e[i].x,e[i].y);

    }

    sort(e+,e+m+,cmp);

    b.make();

    for (int i=;i<=m;i++) swap(e[i].x,e[i].y);

    sort(e+,e+m+,cmp);reverse(e+,e+m+);

    a.make();

    for (int i=;i<=n;i++) e[i].x=b.dfn[i],e[i].y=a.dfn[i];

    sort(e+,e+n+,cmp);

    for (int i=;i<=n;i++)

    {

        for (int j=e[i-].y+;j<=e[i].y;j++) root[j]=root[j-];

        ins(root[e[i].y],,b.cnt,e[i].x);

    }

    for (int i=e[n].y+;i<=a.cnt;i++) root[i]=root[i-];

    while (q--)

    {

        int x=read()+,y=read()+,l=read()+,r=read()+;

        int u=a.geta(x,l),v=b.getb(y,r);

        printf("%d\n",query(root[a.dfn[u]+a.size[u]-],root[a.dfn[u]-],,b.cnt,b.dfn[v],b.dfn[v]+b.size[v]-));

    }

    return ;

}