题解：P17198 [KOI 2026 #2] 杂技

· · 题解

题意简述

Alice 必须始终站在 Bob 左侧。Alice 只能向右走，Bob 只能向左走，两人还可以使用当前位置的任意跳板。对每组起点与终点，判断能否经过若干合法动作到达。

解题思路

把相邻格子之间的空隙编号为 1,2,\dots,N-1。当两人位于 (x,y) 时，用空隙区间 [x,y-1] 表示这个状态。

Alice 向右走会删除区间左端的若干空隙，Bob 向左走会删除区间右端的若干空隙。因此，普通行走只能把当前区间缩小为一个非空子区间。真正需要处理的是能够扩张区间的跳跃。

考虑一块从 x 跳到 y 的跳板。

Alice 向右跳或 Bob 向左跳只会缩小区间，普通行走已经能够完成同样的效果，所以不必单独保留。

对每个空隙 i，记 [l_i,r_i] 为从只包含空隙 i 的状态出发，一次扩张能够覆盖的最远区间。初始有 l_i=r_i=i。所有由空隙 i 触发的向左跳板只需保留最小落点，向右跳板只需保留最大落点。

把每个空隙看作一个有向图结点，并从 i 向区间 [l_i,r_i] 中的每个结点连边。图中的一条边表示：只要当前已经覆盖触发空隙，就可以实际执行一次跳跃，把目标空隙也纳入覆盖范围。

直接连边可能产生平方级边数。建立一棵以空隙为叶子的线段树，并进行如下连边：

从被选中的线段树结点沿儿子边向下，恰好能够到达区间中的全部真实叶子。因此，优化后的图与直接区间连边具有相同的空隙可达关系。图中有 O(N) 个结点和 O(N\log N) 条边。

图中可能存在环。使用非递归 Tarjan 算法求强连通分量，并将图缩成 DAG。对每个分量，先记录其中真实空隙叶子的最小和最大编号。Tarjan 弹出分量的顺序是缩点图的逆拓扑序，所有出边指向的分量都会更早弹出。因此，按照分量编号递增处理，可以用所有后继的答案更新当前分量。

由此可得每个空隙 i 能到达的最小与最大空隙，分别记为 L_i 与 R_i。从单个空隙出发的可达集合一定连续：初始集合是一个点，而每次操作都向当前集合中的某个点加入一个包含该点的区间，取并后仍是区间。因此其完整闭包就是 [L_i,R_i]。

询问的起始状态 (a,b) 覆盖连续空隙 [a,b-1]。从这些起点出发的所有闭包取并，最终边界为：

L=\min_{a\le i<b}L_i

右端为：

R=\max_{a\le i<b}R_i

每个区间 [L_i,R_i] 都包含 i，而所有 i 连续，所以这些区间的并仍是完整区间 [L,R]。每次图上的扩张都能通过先行走到对应跳板、再使用跳板实现。因此两人可以先把范围扩张到所需边界，再通过行走删去两侧多余部分。

目标状态 (c,d) 对应空隙区间 [c,d-1]，它可达当且仅当：

L\le c\land d-1\le R

分别对 L_i 建立区间最小值稀疏表，对 R_i 建立区间最大值稀疏表，即可 O(1) 回答每次询问。总时间复杂度为 O(N\log N+M+Q)，空间复杂度为 O(N\log N)。

正确性证明

普通行走只能缩小空隙区间。所有能够扩大区间的动作恰好是 Alice 向左跳和 Bob 向右跳，并分别对应从触发空隙到所覆盖区间的有向边。若触发空隙已经覆盖，两人总能保持另一人在区间另一侧，先走到跳板再完成该次扩张；反之，任何实际扩张也必然产生图中的对应转移。因此实际可扩张空隙与图中的可达空隙完全相同。

线段树结点向儿子的边只负责展开区间，叶子向区间分解结点的边恰好覆盖 [l_i,r_i]，故线段树图没有增加或遗漏任何真实叶子间的可达关系。Tarjan 缩点保持可达性，逆拓扑动态规划又准确汇总每个分量能够到达的最小和最大真实空隙，所以求得的 [L_i,R_i] 是单空隙的完整可达闭包。

起始状态覆盖 [a,b-1] 的所有空隙。各单点闭包都包含自己的起点，连续起点的闭包之并没有空洞，其边界正是区间最小的 L_i 与区间最大的 R_i。扩张完成后，Alice 与 Bob 可以相向行走，得到闭包内任意非空子区间。因此目标区间可达恰好等价于 L\le c 且 d-1\le R，算法的每个回答均正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
const int V=524293;
const int E=8000005;
const int K=20;
int head[V],to[E],nxt[E],cnt;
int lo[N],hi[N];
int dfn[V],low[V],tim,id[V],cc;
bool ins[V];
int stk[V],top,dfs[V],it[V];
int chead[V],cnxt[V],cl[V],ch[V];
int lg[N],mn[K][N],mx[K][N];
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
void tarjan(int s)
{
    int tp=0;
    dfs[0]=s;
    it[0]=head[s];
    dfn[s]=low[s]=++tim;
    stk[++top]=s;
    ins[s]=1;
    while(tp>=0)
    {
        int x=dfs[tp];
        int &i=it[tp];
        if(i)
        {
            int y=to[i];
            i=nxt[i];
            if(!dfn[y])
            {
                dfn[y]=low[y]=++tim;
                stk[++top]=y;
                ins[y]=1;
                dfs[++tp]=y;
                it[tp]=head[y];
            }
            else if(ins[y])low[x]=min(low[x],dfn[y]);
        }
        else
        {
            if(low[x]==dfn[x])
            {
                cc++;
                while(1)
                {
                    int y=stk[top--];
                    ins[y]=0;
                    id[y]=cc;
                    if(y==x)break;
                }
            }
            tp--;
            if(tp>=0)low[dfs[tp]]=min(low[dfs[tp]],low[x]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int g=n-1;
    for(int i=1;i<=g;i++)lo[i]=hi[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(y<x&&x<=g)lo[x]=min(lo[x],y);
        if(y>x&&x>=2)hi[x-1]=max(hi[x-1],y-1);
    }
    int b=1;
    while(b<g)b<<=1;
    int vc=b*2-1;
    for(int i=1;i<b;i++)
    {
        add(i,i<<1);
        add(i,i<<1|1);
    }
    for(int i=1;i<=g;i++)
    {
        int x=b+i-1;
        int l=b+lo[i]-1,r=b+hi[i]-1;
        while(l<=r)
        {
            if(l&1)add(x,l++);
            if(!(r&1))add(x,r--);
            l>>=1;
            r>>=1;
        }
    }
    for(int i=1;i<=vc;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int i=1;i<=cc;i++)cl[i]=g+1;
    for(int i=1;i<=g;i++)
    {
        int j=id[b+i-1];
        cl[j]=min(cl[j],i);
        ch[j]=max(ch[j],i);
    }
    for(int i=1;i<=vc;i++)
    {
        cnxt[i]=chead[id[i]];
        chead[id[i]]=i;
    }
    for(int i=1;i<=cc;i++)
    {
        for(int j=chead[i];j;j=cnxt[j])
        {
            for(int k=head[j];k;k=nxt[k])
            {
                int y=id[to[k]];
                if(y==i)continue;
                cl[i]=min(cl[i],cl[y]);
                ch[i]=max(ch[i],ch[y]);
            }
        }
    }
    for(int i=1;i<=g;i++)
    {
        int j=id[b+i-1];
        mn[0][i]=cl[j];
        mx[0][i]=ch[j];
    }
    for(int i=2;i<=g;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<K;i++)
    {
        int len=1<<i;
        for(int j=1;j+len-1<=g;j++)
        {
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+(len>>1)]);
            mx[i][j]=max(mx[i-1][j],mx[i-1][j+(len>>1)]);
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int l=a,r=b-1;
        int k=lg[r-l+1];
        int p=r-(1<<k)+1;
        int x=min(mn[k][l],mn[k][p]);
        int y=max(mx[k][l],mx[k][p]);
        cout<<(x<=c&&d-1<=y?"YES":"NO")<<'\n';
    }
    return 0;
}