【IOI2018】狼人 | Mrsrz's blog

Kruskal重构树，二维数点

题目大意：

给定一张 $n$ 个点 $m$ 条边的无向连通图，点的编号为 $0\sim n-1$。

你有两个状态，人形和狼形。

每组询问给出 $u,v,l,r$，你从 $u$ 出发开始时为人形，人形只能在编号大于等于 $l$ 的点之间移动，要求到达 $v$，且变为狼形，狼形只能在编号小于等于 $r$ 的点之间移动。可以在编号在 $[l,r]$ 的点里从人形变成狼形。

每组询问要回答是否存在一种合法的走法。

题解：

对原图建 Kruskal 重构树，那么人形和狼形能到达的区域，就是其对应的重构树中的一个子树。找这棵子树，就直接在重构树上倍增即可。

这里的重构树是基于点权的，而且互不相同，所以可以贪心建树。

然后，我们需要知道，人形和狼形对应子树中，是否存在一个点，在两棵子树中都有出现。

我们对两棵重构树分别求出 dfs 序，则一个结点的信息 $(\mathrm{dfn}_{1,i},\mathrm{dfn}_{2,i})$ 可以看成二维平面上的点。

然后，一棵子树对应的 dfs 序是连续的，那么相当于询问一个矩形区域内是否存在点。

于是转化为二维数点问题。用离线树状数组解决即可。

时间复杂度 $O((n+m+q)\log n)$。

Code：

//#define UOJ
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#ifdef UOJ
#include"werewolf.h"
#endif
using namespace std;
typedef vector<int>VI;
#ifdef ONLINE_JUDGE
const int N=4e5+8;
#else
const int N=31;
#endif
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],cnt;
inline bool Leq(int a,int b){return a<=b;}
inline bool Geq(int a,int b){return a>=b;}
struct Kruskal_Tree{
    int dad[N],n,fa[N],dfn[N],idx,F[19][N],d[N],sz[N],idfn[N];
    VI G[N];
    inline int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);}
    typedef bool(*func)(int,int);
    func fc;
    void dfs(int now){
        idfn[dfn[now]=++idx]=now;sz[now]=1;
        for(int i=0;i<G[now].size();++i){
            int to=G[now][i];
            fa[to]=now;
            F[0][to+1]=now+1;
            dfs(to);
            sz[now]+=sz[to];
        }
    }
    int jump(int x,int k){
        ++x;
        for(int i=18;~i;--i)
            if(F[i][x]&&fc(d[F[i][x]-1],k))x=F[i][x];
        return x-1;
    }
    inline void merge(int u,int v){
        int y=find(v);
        if(y==u)return;
        dad[y]=u;
        G[u].push_back(y);
    }
    void init(int nn,bool tag,bool(*Cmp)(int,int)){
        fc=Cmp;
        n=nn;
        for(int i=0;i<n;++i)dad[i]=i,d[i]=i;
        if(tag){
            for(int u=nn-1;~u;--u)
                for(int i=head[u];i;i=e[i].nxt)
                    if(u<e[i].to)
                        merge(u,e[i].to);
        }else{
            for(int u=0;u<nn;++u)
                for(int i=head[u];i;i=e[i].nxt)
                    if(e[i].to<u)
                        merge(u,e[i].to);
        }
        dfs(tag?0:nn-1);
        for(int i=1;i<19;++i)
            for(int j=1;j<=n;++j)
                F[i][j]=F[i-1][F[i-1][j]];

    }
    inline void get(int u,int k,int&L,int&R){
        u=jump(u,k);
        L=dfn[u],R=dfn[u]+sz[u]-1;
    }
}a,b;
VI ret;
struct ques{
    int l,r,fh,id;
};
vector<ques>q[N];
int B[N],n;
inline void add(int i){for(;i<=n;i+=i&-i)++B[i];}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
VI check_validity(int n,VI X,VI Y,VI S,VI E,VI L,VI R){
    ret.clear();
    ret.resize(S.size());
    for(int i=0;i<X.size();++i){
        int x=X[i],y=Y[i];
        e[++cnt]=(edge){y,head[x]},head[x]=cnt;
        e[++cnt]=(edge){x,head[y]},head[y]=cnt;
    }
    a.init(n,1,Geq);b.init(n,0,Leq);
    for(int i=0;i<S.size();++i){
        int u=S[i],v=E[i],l=L[i],r=R[i];
        if(u<l||r<v)continue;
        int L1,L2,R1,R2;
        a.get(u,l,L1,R1);b.get(v,r,L2,R2);
        q[L1-1].push_back((ques){L2,R2,-1,i});
        q[R1].push_back((ques){L2,R2,1,i});
    }
    ::n=n;
    for(int i=1;i<=n;++i){
        add(b.dfn[a.idfn[i]]);
        for(int it=0;it<q[i].size();++it){
            int l=q[i][it].l,r=q[i][it].r,id=q[i][it].id,fh=q[i][it].fh;
            ret[id]+=fh*(ask(r)-ask(l-1));
        }
    }
    for(int i=0;i<S.size();++i)
        if(ret[i]>0)ret[i]=1;else ret[i]=0;
    return ret;
}
#ifndef UOJ
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    VI X,Y,S,E,L,R;
    for(int i=0;i<m;++i){
        int x,y;
        cin>>x>>y;
        X.push_back(x),Y.push_back(y);
    }
    for(int i=0;i<q;++i){
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        S.push_back(u),E.push_back(v),L.push_back(l),R.push_back(r);
    }
    VI ret=check_validity(n,X,Y,S,E,L,R);
    for(int i=0;i<ret.size();++i)
        cout<<ret[i]<<'\n';
    return 0;
}
#endif