题解：P10100 [ROIR 2023] 石头 (Day 2)

· · 题解

注意到整个涂色过程本质上就是维护一个白色区间 [L,R] 不断向两侧扩张。每次扩张时，比较 a_{L-1} 和 a_{R+1} 的大小，哪个小就往哪边扩。这提示我们，扩张方向完全由区间两侧的最大值决定。

考虑固定终点 p，假设从某个起点 i 出发。不妨设 i < p（起点在终点左边），那么白色区间必须向右扩张到 p。设向左扩张了 l 步，向右扩张了 r 步，则有 k = l + r + 1，其中 l = p - i 是必须向右走的步数。

现在问题转化为：给定起点和步数限制，如何判断能否在第 k 步恰好到达 p？我们发现，在扩张过程中，当白色区间已经覆盖到某个位置 mid 时，下一步往左还是往右，取决于 \max(a_{L..mid}) 和 \max(a_{mid+1..R}) 的大小关系。如果左边最大值更小，就会优先向左扩张，从而阻碍向右推进。

这启发我们用 ST 表维护区间最大值，这样就能 O(1) 判断任意时刻的扩展方向。

接下来考虑求解。对于固定的 (p,k)，我们发现满足条件的起点构成一个连续区间。这是自然的——如果两个起点都能在 k 步内到达 p，那么它们之间的所有起点也必然满足条件。

于是可以对起点位置二分。对于 i>p 的情况，二分最远的 i，使得 [p,i-1] 的最大值大于 [i+1,p+k] 的最大值（这样右边更小，会优先向右扩）。对于 i< p 的情况对称处理。

设 F(p,k) 表示在第 k 步或之前到达 p 的起点个数。那么恰好第 k 步到达的数量就是 F(p,k) - F(p,k-1)。F(p,k) 通过上述二分即可求出。

时间复杂度 O(n\log n + q\log n)。

细节详见代码。

#include<bits/stdc++.h>
#define N 100005
#define M 17
#define endl '\n'
using namespace std;

int n,q,a[N],st[M][N],lg[N];

int query(int l,int r){
    if(l<1||l>r||r>n) return 1e9;
    int t=lg[r-l+1];
    return max(st[t][l],st[t][r-(1<<t)+1]);
}
int sum(int p,int k){
    if(k==1) return 1;
    if(k==0) return 0;
    int res=0;
    int l=p+1,r=min(n,p+k-1),ans=p;
    while(l<=r){
        int mid=l+r>>1;
        if(query(p,mid-1)<query(mid+1,p+k)){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    res+=ans-p;
    l=max(1,p-k+1),r=p-1,ans=p;
    while(l<=r){
        int mid=l+r>>1;
        if(query(mid+1,p)<query(p-k,mid-1)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    res+=p-ans;
    return res+1;
}

signed main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    lg[1]=0;
    for(int i=2;i<=n;i++){
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++){
        st[0][i]=a[i];
    }
    for(int i=1;i<=lg[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
        }
    }
    while(q--){
        int p,k;
        scanf("%d%d",&p,&k);
        printf("%d\n",sum(p,k)-sum(p,k-1));
    }
    return 0;
}