题解：P12018 [NOISG 2025 Finals] 机器人

· · 题解

[NOISG 2025 Finals] 机器人

由于特殊方块的分布性质，将终点看作特殊方块，每个特殊方块相当于可以走到上一行/下一行的紧靠右的那个特殊方块，那么只需要关注特殊方块之间的移动：

相当于询问左边 [l,r] 的点跳特殊点可以跳到的最小本质不同终点个数。

然后进行一个 \texttt{observation}，观察发现对于一个固定的特殊点，能够走到这个点的起点一定是一个区间。

证明：

首先肯定有一个能一直往下走和一直往上走到达目标结束点的出发点。

那么 (x+1),(x-1) 可以接上第一个拐点（由于连边连最靠右的所以肯定不会被挡住），然后走到终点，这样归纳下去整个区间内都可以到达，因此可以到达这个终点的所有起点构成一个区间。

于是考虑定义能走到终点 x 的最上节点为 L_x，最下为 R_x，那么 [L_x,R_x] 中的所有点都能走到 x。于是询问就是能覆盖一个初始区间的最少终止节点个数。可以直接贪，每次找一个 L_x 能覆盖住区间的最大 R_x 即可。

但是复杂度不对，考虑倍增，定义 f_{i,k} 表示从左端点为 i 开始跳，跳 2^k 个区间能够跳到的最远右端点，每次倍增往上拼区间即可。时间复杂度 O((n+q)\log n)。

:::info[代码]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define psb push_back

using namespace std;

template<class T>void Max(T &x,T y) { if (y>x) x=y; }
template<class T>void Min(T &x,T y) { if (y<x) x=y; }
const int N=200010,T=18;
int n,m,Q;
int sp[N];
int lst[N];
vector<int> pre[N],ed[N];
int ll[N],rr[N],L[N],R[N];
int mxr[N];
int f[T][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    for (int j=1;j<=m;j++) cin >> sp[j];

    for (int i=0;i<=n+1;i++) lst[i]=m+1;
    for (int j=m;j>=1;j--)
    {
        int i=sp[j]; 
        if (lst[i-1]!=m+1) pre[lst[i-1]].psb(j);
        else ed[i-1].psb(j);
        if (lst[i+1]!=m+1) pre[lst[i+1]].psb(j);
        else ed[i+1].psb(j);
        lst[i]=j;
    }
    memset(lst,0,sizeof(lst));
    for (int j=1;j<=m;j++)
    {
        int i=sp[j];
        ll[j]=1e9,rr[j]=0;
        if (!lst[i]) ll[j]=rr[j]=i;
        auto upd = [&](int x)
        {
            if (x)
            {
                Min(ll[j],ll[x]);
                Max(rr[j],rr[x]);
            }
        };
        for (int x : pre[j]) upd(x);
        lst[i]=j;
    }
    for (int i=0;i<=n+1;i++)
    {
        L[i]=1e9,R[i]=0;
        if (!lst[i]) L[i]=R[i]=i;
        auto upd = [&](int x)
        {
            if (x)
            {
                Min(L[i],ll[x]);
                Max(R[i],rr[x]);
            }
        };
        for (int x : ed[i]) upd(x);
    }

    //for (int i=0;i<=n+1;i++) cout << L[i] << " " << R[i] << "\n";
    memset(mxr,-1,sizeof(mxr));
    for (int i=0;i<=n+1;i++) 
    {
        if (L[i]>R[i]) continue;
        Max(mxr[L[i]],R[i]);
    }

    memset(f,-1,sizeof(f));
    int mx=-1;
    for (int i=0;i<=n+1;i++)
    {
        Max(mx,mxr[i]);
        f[0][i]=mx;
    }
    for (int k=1;k<T;k++)
    {
        for (int i=1;i<=n;i++)
        {
            int p=f[k-1][i];
            if (p!=-1 && f[k-1][p+1]!=-1) f[k][i]=f[k-1][p+1];
        }
    }

    cin >> Q;
    while (Q--)
    {
        int l,r;
        cin >> l >> r;
        int ans=0;
        for (int k=T-1;~k;k--)
        {
            int p=f[k][l];
            if (p!=-1 && p<r)
            {
                ans+=(1<<k);
                l=p+1;
            }
        }
        cout << ans+1 << "\n";
    }

    return 0; 
}

:::