P4899 [IOI2018] werewolf 狼人 题解

题目描述

省流：

\(n\) 个点，\(m\) 条边，\(q\) 次询问，对于每一次询问，给定一个起点 \(S\) 和终点 \(T\) ，能否找到一条路径，前半程不能走 \(0\thicksim L-1\) 这些点，后半程不能走 \(R+1\thicksim N-1\) 这些点。中途必须有一个点在\(L\thicksim R\)之间。

题目分析

首先对于这种限定了走的边的属性，或者走的点的属性的路径题，自然想到Kruskal重构树，然后注意到城市从 \(0\) 开始标号很可恶，所以我们就可以将所有标号加一，并且转化题意，对于前半段，我们只走 \(L\thicksim N\) 这些点，对于后半程，我们只走 $1\thicksim R $ 这些点，那么对于这样的要求，我们就可以建立Kruskal重构树了。首先分析边的权值，我们知道，走了一条边，就意味着会经过这条边连接的两个端点，所以说对于前半段来说，我们可以以\(min(x,y)\)为边权，从大到小排序建立一棵Kruskal重构树。因为我们对一条边所定的限制，就是尽量走大的编号，而界定前半程能否走这一条边的限制，即是会不会走到因为太小而不合法的编号，而对于后半程来说，同理可得，以\(max(x,y)\)为边权，从小到大排序建立一棵Kruskal重构树。

那么建立好重构树之后，我们就可以将路程分为三段，前半程，转折点，后半程，那么前半程和后半程都必须可达这个转折点，所以合法的转折点也就是前半程可达的点和后半程可达的点的交集。那么我们可以在前半程的Kruskal重构树上跳到权值大于等于\(L\)的最浅的结点，那么前半程可达的点一定在该点的子节点之中，对于后半程同理，于是我们就将问题转化成了求这样两个节点囊括的子节点有没有交集。

对于这样的问题，我们可以使用主席树解决。我们都知道一个点的编号与其\(dfn\)序是一一对应的，所以我们暂时可以用\(dfn\)序代替点的标号，我们在两棵树上先跑一个\(dfn\)序，然后按照前半程树的\(dfn\)序来将后半程的\(dfn\)加入主席树。当我们对于一个查询的时候，我们只需要先将前半程对应的祖先的所囊括的子节点的\(dfn\)序的左右端点作为查询的左右两数，让后查询是否存在值在所询问的后半程对应的祖先的\(dfn\)序的左右端点之间，如果存在，说明有一个点是它们的交集。（这段确实不好理解）

代码部分（因为有两个重构树，所以写的Class）

/*
 * Author:Ehundategh
 * Update:2023/10/17
 * Title:P4899 [IOI2018] werewolf 狼人.cpp
 * You steal,I kill
 */
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 800010
#define MAXM 800010
#define LSon Node[Now].LeftS
#define RSon Node[Now].RightS
using namespace std;
int n,m,q,In1,In2,In3,In4;
template <typename T> inline void read(T &x){
    int f=0;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar())f|=(c=='-');
    for(;isdigit(c);c=getchar())x=((x<<3)+(x<<1)+(c^48));
    x=f?-x:x;
}
struct edge{
    int St,Ed;
}Edge[MAXM];
bool cmpman(edge a,edge b){return min(a.St,a.Ed)>min(b.St,b.Ed);}
bool cmpwolf(edge a,edge b){return max(a.St,a.Ed)<max(b.St,b.Ed);}
class President_Tree{
private:
    int cnt=0;
    struct node{
        int Left,Right;
        int LeftS,RightS;
        int Sum;
    }T[MAXN<<5];
public:
    int Roots[MAXN];
    int New_Tree(int Last,int Left,int Right,int Value){
        int Root=++cnt;
        T[Root].LeftS=T[Last].LeftS;
        T[Root].RightS=T[Last].RightS;
        T[Root].Sum=T[Last].Sum+1;
        T[Root].Left=Left;T[Root].Right=Right;
        int Mid=(Left+Right)/2;
        if(Left!=Right){
            if(Value<=Mid){T[Root].LeftS=New_Tree(T[Last].LeftS,Left,Mid,Value);}
            else{T[Root].RightS=New_Tree(T[Last].RightS,Mid+1,Right,Value);}
        }
        return Root;
    }
    int Query(int Pl,int Pr,int Left,int Right){
        if(T[Pr].Left>=Left&&T[Pr].Right<=Right){
            return T[Pr].Sum-T[Pl].Sum;
        }
        else if(T[Pr].Right<Left||T[Pr].Left>Right) return 0;
        else return (Query(T[Pl].LeftS,T[Pr].LeftS,Left,Right)|Query(T[Pl].RightS,T[Pr].RightS,Left,Right));
    }
}President;
class Kruskal{
private:
    int Fa[MAXN<<1][21],Father[MAXN<<1];
public:
    struct node{
        int LeftS,RightS,Left,Right,Value;
    }Node[MAXN<<1];
    int cnt,DFN[MAXN],cnd=0,Line[MAXN];
    int Find(int a){return Father[a]==a?Father[a]:Father[a]=Find(Father[a]);}
    void Merge(int a,int b,int c,int Type){
        int Faa=Find(a),Fab=Find(b);
        Father[Faa]=Father[Fab]=c;
        Fa[Faa][0]=Fa[Fab][0]=c;
        Node[c].LeftS=Faa;Node[c].RightS=Fab;
        if(Type==0) Node[c].Value=min(a,b);
        else Node[c].Value=max(a,b);
    }
    void Build(int Type){
        cnt=n;
        for(int i=1;i<=2*n;i++) Father[i]=i,Fa[i][0]=i;
        if(Type==0) sort(Edge+1,Edge+m+1,cmpman);
        else sort(Edge+1,Edge+m+1,cmpwolf);
        for(int i=1;i<=m;i++){
            if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;
            Merge(Edge[i].St,Edge[i].Ed,++cnt,Type);
        }
    }
    void Pre(){
        for(int i=1;i<=cnt;i++){
            if(Fa[i][0]==i) DFS(i);
        }
    }
    void DFS(int Now){
        Node[Now].Left=1<<30;
        Node[Now].Right=0;
        if(!(LSon||RSon)) {
            DFN[Now]=Node[Now].Left=Node[Now].Right=++cnd;
            Line[DFN[Now]]=Now;
            return;
        }
        DFS(LSon),Node[Now].Left=min(Node[Now].Left,Node[LSon].Left),Node[Now].Right=max(Node[Now].Right,Node[LSon].Right);
        DFS(RSon),Node[Now].Left=min(Node[Now].Left,Node[RSon].Left),Node[Now].Right=max(Node[Now].Right,Node[RSon].Right);
    }
    void Init(){
        for(int i=1;i<=19;i++){
            for(int j=1;j<=cnt;j++){
                Fa[j][i]=Fa[Fa[j][i-1]][i-1];
            }
        }
    }
    int Jump(int Now,int Type,int Top){
        for(int i=19;i>=0;i--){
            if(Type==0&&Node[Fa[Now][i]].Value>=Top) Now=Fa[Now][i];
            else if(Type==1&&Node[Fa[Now][i]].Value<=Top) Now=Fa[Now][i];
        }
        return Now;
    }
}T1,T2;
void Init_President(){
    for(int i=1;i<=n;i++){
        President.Roots[i]=President.New_Tree(President.Roots[i-1],1,n,T2.DFN[T1.Line[i]]);
//        printf("%d %d\n",i,T2.DFN[T1.Line[i]]);
    }
}
bool Judge(int S,int T,int L,int R){
    S=T1.Jump(S,0,L);
    T=T2.Jump(T,1,R);
//    printf("%d %d %d %d\n",T1.Node[S].Left-1,T1.Node[S].Right,T2.Node[T].Left,T2.Node[T].Right);
    int Temp=President.Query(President.Roots[T1.Node[S].Left-1],President.Roots[T1.Node[S].Right],T2.Node[T].Left,T2.Node[T].Right);
    if(Temp) return true;
    else return false;
}
int main(){
    read(n);read(m);read(q);
    for(int i=1;i<=m;i++){
        read(Edge[i].St);read(Edge[i].Ed);
        Edge[i].St++;
        Edge[i].Ed++;
    }
    T1.Build(0);T2.Build(1);
    T1.Pre();T2.Pre();
    T1.Init();T2.Init();
    Init_President();
    while(q-->0){
        read(In1);read(In2);read(In3);read(In4);
        In1++;In2++;In3++;In4++;
        if(Judge(In1,In2,In3,In4)) puts("1");
        else puts("0");
    }
    return 0;
}

如果觉得这篇题解让你有所收获，就点个赞吧。