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;
}

如果覺得這篇題解讓你有所收穫，就點個贊吧。