题解洛谷 P4899 【[IOI2018] werewolf 狼人】

先考虑狼形，其只能走编号小于\(R\)的点。若将每条边赋边权为其两端点编号的较大值，然后按最小生成树的顺序构建\(Kruskal\)重构树。

那么从原图的一个点\(x\)在树上倍增，到达满足要求且深度最浅的节点，该节点子树内所有原图中的点，狼形从\(x\)都能到达。

同样的，人形构建重构树就是边权为两端点编号的较小值，按最大生成树的顺序。

先构建这两棵\(Kruskal\)重构树，对于每次询问，只需查询起点和终点分别树上倍增后子树内的节点是否有交即可。

判断有交可以通过\(dfs\)序。设两棵重构树分别为\(A\)和\(B\)，对于一个点在两棵树上的\(dfs\)序看作点对的形式\((dfn_A,dfn_B)\)。因为子树中的\(dfs\)序都是连续的，所以就把问题转化为二维数点。可以对\(dfn_A\)这一维构建主席树，\(dfn_B\)作为权值插入，判断有交只需看矩形中是否存在点即可。

具体实现看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 1200010

#define maxm 10000010

#define inf 1000000000

#define mid ((l+r)>>1)

using namespace std;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,m,q,tree_cnt;

int p[maxn],rt[maxn],cnt[maxm],ls[maxm],rs[maxm];

struct Edge

{

    int x,y;

}ed[maxn];

bool cmp1(const Edge &a,const Edge &b)

{

    return max(a.x,a.y)<max(b.x,b.y);

}

bool cmp2(const Edge &a,const Edge &b)

{

    return min(a.x,a.y)>min(b.x,b.y);

}

struct node

{

    int tot,dfn_cnt;

    int val[maxn],fa[maxn],f[maxn][25],in[maxn],out[maxn];

    struct edge

    {

        int to,nxt;

    }e[maxn];

    int head[maxn],edge_cnt;

    void add(int from,int to)

    {

        e[++edge_cnt]=(edge){to,head[from]};

        head[from]=edge_cnt;

    }

    int find(int x)

    {

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

    }

    void dfs(int x)

    {

        for(int i=1;i<=20;++i) f[x][i]=f[f[x][i-1]][i-1];

        in[x]=++dfn_cnt;

        for(int i=head[x];i;i=e[i].nxt) dfs(e[i].to);

        out[x]=dfn_cnt;

    }

    void build(int type)

    {

    	tot=n;

        if(!type) sort(ed+1,ed+m+1,cmp1);

        else sort(ed+1,ed+m+1,cmp2);

        for(int i=1;i<=2*n-1;++i) fa[i]=i;

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

        {

            int x=find(ed[i].x),y=find(ed[i].y);

            if(x==y) continue;

            if(!type) val[++tot]=max(ed[i].x,ed[i].y);

            else val[++tot]=min(ed[i].x,ed[i].y);

            add(tot,y),add(tot,x),fa[x]=fa[y]=f[x][0]=f[y][0]=tot;

            if(tot==2*n-1) break;

        }

        dfs(tot);

    }

    int get(int x,int v,int type)

    {

        for(int i=20;i>=0;--i)

        {

            if(!type&&f[x][i]&&val[f[x][i]]<=v) x=f[x][i];

            if(type&&f[x][i]&&val[f[x][i]]>=v) x=f[x][i];

        }

        return x;

    }

}A,B;

bool cmp3(const int &a,const int &b)

{

    return A.in[a]<A.in[b];

}

void modify(int l,int r,int pos,int v,int &cur)

{

    int x=++tree_cnt;

    ls[x]=ls[cur],rs[x]=rs[cur],cnt[x]=cnt[cur]+v,cur=x;

    if(l==r) return;

    if(pos<=mid) modify(l,mid,pos,v,ls[cur]);

    else modify(mid+1,r,pos,v,rs[cur]);

}

int query(int L,int R,int l,int r,int x,int y)

{

    if(L<=l&&R>=r) return cnt[y]-cnt[x];

    int v=0;

    if(L<=mid) v+=query(L,R,l,mid,ls[x],ls[y]);

    if(R>mid) v+=query(L,R,mid+1,r,rs[x],rs[y]);

    return v;

}

int main()

{

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

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

    {

        read(ed[i].x),read(ed[i].y);

        ed[i].x++,ed[i].y++;

    }

    A.build(0),B.build(1);

    for(int i=1;i<=2*n-1;++i) p[i]=i;

    sort(p+1,p+2*n,cmp3);

    for(int i=1;i<=2*n-1;++i)

        rt[i]=rt[i-1],modify(1,2*n-1,B.in[p[i]],p[i]<=n,rt[i]);

    while(q--)

    {

        int x,y,l,r;

        read(x),read(y),read(l),read(r);

        x++,y++,l++,r++,x=B.get(x,l,1),y=A.get(y,r,0);

        if(query(B.in[x],B.out[x],1,2*n-1,rt[A.in[y]-1],rt[A.out[y]])) puts("1");

        else puts("0");

    }

    return 0;

}

巴特西

题解洛谷 P4899 【[IOI2018] werewolf 狼人】

最新文章

热门文章

巴特西

题解 洛谷 P4899 【[IOI2018] werewolf 狼人】

最新文章

热门文章

题解洛谷 P4899 【[IOI2018] werewolf 狼人】