【IOI 2018】Werewolf / Solution

Description

官方 PDF 题面

Idea

相当于询问是否存在一个中间点 $X$，满足 $S_i$ 能仅经过编号 $≥ L_i$ 的点走到 $X$，且 $E_i$ 能仅经过编号 $≤ R_i$ 的点走到 $X$。

考虑第一部分，第二部分类似。把边权设置成 $min(A_i, B_i)$，然后求一个 Kruskal 重构树。即模拟 Kruskal 求最小生成树的过程，每次加入一条边时，就新建一个表示这条边的节点，作为那两个点的父亲。

于是 $S_i$ 仅经过编号 $≥ L_i$ 的点能到达的所有点就都在某个子树中——从 $S_i$ 往上倍增找到最浅的 $≥ L_i$ 的那个点的子树。

$E_i$ 那部分同理。

下面询问是否存在一个点同时在两棵子树内，主席树查询 DFS 序即可。

Code

#include <bits/stdc++.h>
#define maxn 200100
using namespace std;
int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*flag;
}
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
};
Edge raw_edge[maxn<<2];
int raw_head[maxn],val[maxn];
int cnt,n,m,q;
void Raw_Add(int a,int b){
    raw_edge[++cnt]=Edge(b,raw_head[a]);
    raw_head[a]=cnt;
}
struct Tree{
    Edge l[maxn<<2];
    int cnt,tot,tim,dft;
    int p[20][maxn],fa[maxn];
    int dfn[maxn],head[maxn],low[maxn];
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void Add(int a,int b){
        l[++cnt]=Edge(b,head[a]);
        head[a]=cnt;
    }
    void Kruskal(){
        for (int i=1;i<=n;++i)
            fa[i]=i;
        if (dft) for (int u=n;u;--u){
            for (int i=raw_head[u];i;i=raw_edge[i].next){
                int v=raw_edge[i].to;if (v>u){
                    int fx=find(u),fy=find(v);
                    if (fx==fy) continue;
                    fa[fy]=fx;Add(fx,fy);
                    if (++tot==n-1) return;
                }
            }
        }
        else for (int u=1;u<=n;++u){
            for (int i=raw_head[u];i;i=raw_edge[i].next){
                int v=raw_edge[i].to;if (v<u){
                    int fx=find(u),fy=find(v);
                    if (fx==fy) continue;
                    fa[fy]=fx;Add(fx,fy);
                    if (++tot==n-1) return;
                }
            }
        }
    }
    void Dfs(int u,int f){
        dfn[u]=++tim;
        p[0][u]=f;
        for (int i=1;i<20;++i)
            p[i][u]=p[i-1][p[i-1][u]];
        for (int i=head[u];i;i=l[i].next){
            int v=l[i].to;if (v==f) continue;
            Dfs(v,u);
        }
        low[u]=tim;
    }
    void Jump(int &u,int k){
        if (dft) for (int i=19;~i;--i){
            if (p[i][u]&&(p[i][u]>=k)) u=p[i][u];}
        else for (int i=19;~i;--i)
            if (p[i][u]&&p[i][u]<=k) u=p[i][u];
    }
    void Build(int mark){
        dft=mark;Kruskal();
        if (mark) Dfs(1,0);
        else Dfs(n,0);
    }
}Max,Min;
struct President_Tree{
    #define mid ((l+r)>>1)
    int cnt,rt[maxn],t[maxn<<6];
    int ls[maxn<<6],rs[maxn<<6];
    void Update(int &p,int pre,int l,int r,int x){
        if (!p) p=++cnt;t[p]=t[pre]+1;
        if (l==r) return;
        if (mid>=x) rs[p]=rs[pre],Update(ls[p],ls[pre],l,mid,x);
        else ls[p]=ls[pre],Update(rs[p],rs[pre],mid+1,r,x);
    }
    int Query(int lp,int rp,int l,int r,int L,int R){
        if (L<=l&&r<=R) return t[rp]-t[lp];
        if (mid>=R) return Query(ls[lp],ls[rp],l,mid,L,R);
        if (mid<L) return Query(rs[lp],rs[rp],mid+1,r,L,R);
        return Query(ls[lp],ls[rp],l,mid,L,R)+Query(rs[lp],rs[rp],mid+1,r,L,R);
    }
}T;
int main(){
    n=read(),m=read(),q=read();
    for (int i=1;i<=m;++i){
        int u=read()+1,v=read()+1;
        Raw_Add(u,v),Raw_Add(v,u);
    }
    Max.Build(0),Min.Build(1);
    for (int i=1;i<=n;++i)
        val[Min.dfn[i]]=Max.dfn[i];
    for (int i=1;i<=n;++i)
        T.Update(T.rt[i],T.rt[i-1],1,n,val[i]);
    for (int i=1;i<=q;++i){
        int s=read()+1,t=read()+1,l=read()+1,r=read()+1;
        Min.Jump(s,l);Max.Jump(t,r);
        bool Mid=T.Query(T.rt[Min.dfn[s]-1],T.rt[Min.low[s]],
            1,n,Max.dfn[t],Max.low[t]);
        puts(Mid?"1":"0");
    }
    return 0;
}