LOJ

UOJ

Luogu

分析

以端点的 $\min$ 为边权建一棵 Kruskal 重构树，以端点的 $\max$ 为边权建一棵 Kruskal 重构树。

那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点，其子树就是人类状态下从起点出发能走到的点；在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点，其子树就是狼人状态下能走到终点的点。

那么我们只需要求这两棵子树中的点有没有交。我们把 DFS 序求出来，把每个点在两棵树上的 DFS 序看成一个点，则相当于问一个矩形内是否有点，直接主席树即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#include "werewolf.h"
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,Q;
vector<int> E[N];

struct H {
    int f[N];
    int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
    void merge(int x,int y) {
        x=find(x),y=find(y);
        if (x!=y) f[x]=y;
    }

    vector<int> T[N];
    int p[18][N],dfn[N],low[N],tim=0;
    void dfs(int u) {
        for (int i=1;i<18;++i) p[i][u]=p[i-1][p[i-1][u]];
        dfn[u]=++tim;
        for (int v:T[u]) dfs(v);
        low[u]=tim;
    }   
    int jump(int u,int lim,int op) {
        for (int i=17;~i;--i) {
            if (!op&&p[i][u]>=lim) u=p[i][u];
            if (op&&p[i][u]&&p[i][u]<=lim) u=p[i][u];
        }
        return u;
    }

    void build(int op) {
        for (int i=1;i<=n;++i) f[i]=i;
        if (!op) {
            for (int u=n;u>=1;--u)
                for (int v:E[u]) {
                    if (u>v) continue;
                    v=find(v);
                    if (u!=v) T[u].emplace_back(v),f[v]=p[0][v]=u;
                }
            dfs(1);
        } else {
            for (int u=1;u<=n;++u)
                for (int v:E[u]) {
                    if (u<v) continue;
                    v=find(v);
                    if (u!=v) T[u].emplace_back(v),f[v]=p[0][v]=u;
                }
            dfs(n);
        }
    }
} A,B;

namespace L {
#define ls(o) t[o].ls
#define rs(o) t[o].rs
    int rt[N],pos[N],tot=0;
    struct node { int ls,rs,sum; } t[N*30];
    void modify(int& o,int f,int l,int r,int p) {
        t[o=++tot]=t[f],++t[o].sum;
        if (l==r) return;
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls(o),ls(f),l,mid,p);
        else modify(rs(o),rs(f),mid+1,r,p);
    }
    int query(int x,int y,int l,int r,int ql,int qr) {
        if (!x&&!y) return 0;
        if (ql<=l&&r<=qr) return t[y].sum-t[x].sum;
        int mid=(l+r)>>1,res=0;
        if (ql<=mid) res+=query(ls(x),ls(y),l,mid,ql,qr);
        if (qr>mid) res+=query(rs(x),rs(y),mid+1,r,ql,qr);
        return res;
    }
#undef ls
#undef rs
}

vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int> S,
                                 vector<int> E,vector<int> L,vector<int> R) {
    ::n=n,m=X.size(),Q=S.size();
    for (int i=0;i<m;++i) {
        int u=X[i]+1,v=Y[i]+1;
        ::E[u].emplace_back(v),::E[v].emplace_back(u);
    }
    A.build(0),B.build(1);
    for (int i=1;i<=n;++i) L::pos[A.dfn[i]]=B.dfn[i];
    for (int i=1;i<=n;++i) L::modify(L::rt[i],L::rt[i-1],1,n,L::pos[i]);
    vector<int> ans;
    for (int i=0;i<Q;++i) {
        int s=S[i]+1,t=E[i]+1,l=L[i]+1,r=R[i]+1;
        s=A.jump(s,l,0),t=B.jump(t,r,1);
        ans.emplace_back(L::query(L::rt[A.dfn[s]-1],L::rt[A.low[s]],1,n,B.dfn[t],B.low[t])?1:0);
    }
    return ans;
}