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

ysw_2029 · 2026-06-04 10:46:22 · 题解

提供一种在线的 O(n\log n+q) 的做法。不需要二分。目前获得了最优解。

对于一组询问 p,k，显然一定是在左边或右边拿了 k-1 个数后再拿到位置 p。

那么一定是得到区间 [p+1,p+k-1] 或 [p-k+1,p-1] 后再向位置 p 拓展的。

由于左右都同理，所以我们只讨论在右边的情况。

则此时是区间 [p+1,p+k-1] 向位置 p 拓展。不妨设 l=p+1,r=p+k-1,q=p+k。

即 l,r 为区间的左右端点，q 为区间右侧紧挨着的点，也是区间不可以拓展到的点。

显然，如果 r>n 则直接无解；如果 a_p>a_q，那么区间 [l,r] 便会直接向位置 q 拓展，也是不合法的。

我们再令 maxx 为区间 [l,r] 的最大值，now 为该最大值的下标（即 a_{now}=maxx)。

然后我们就可以进行分讨：

• 如果 maxx<a_p 的话，由于 a_p<a_q，则区间 [l,r] 内的所有值均小于 a_p 和 a_q。因此，我们从区间内的任意一个位置出发，都一定会拓展到区间 [l,r]，然后再向位置 p 拓展。故答案增加区间的长度，即 r-l+1。

• 否则，我们需要考虑如下三种情况：

  • 当起点在区间 [l,now-1] 时，由于 maxx>a_p 且 maxx>\max\limits_{i=l}^{now-1}a_i，所以在这一段出发的话则会提前拓展到位置 p。显然不合法。
  • 当起点在区间 [now+1,r] 时，则我们需要进一步判断：
  • 如果 a_q>maxx，则显然在将区间 [now+1,r] 完全覆盖后继续向 now 拓展，随后便会拓展到位置 p。则此时答案增加右边这段区间的长度，即 r-(now+1)+1=r-now；
  • 否则，显然在遇到位置 now 之前或之后便不断向右拓展，拿到位置 q。则此时无解。
  • 当起点在位置 now 时，不妨设 lmax 为区间 [l,now-1] 的最大值，rmax 为区间 [now+1,r] 的最大值。如果不存在区间的话则最大值为 0。此时：
  • 如果 lmax>a_q，则我们会在遇到 lmax 后向右拓展到位置 q，不合法；
  • 如果 rmax>a_q，显然此时 lmax<a_q，所以我们会在遇到 rmax 后向左拓展提前拿到位置 p，不合法；
  • 否则，如果 rmax>lmax 且 rmax>a_p，则我们也会在遇到 rmax 后向左拿到位置 p，不合法；
  • 否则，就没有情况会阻止我们从 [l,r] 拓展到位置 p，此时答案加一。

于是乎我们就分讨完了。注意如果 k=1 的话上面的讨论是错误的，所以直接特判即可。

以及由于我们不可能拓展到位置 0 或 n+1，所以需要让这两个位置赋值为一个较大值，比如 n+1。

而我们的分讨中只需要求静态区间最大值及其下标，用 st 表维护即可。

时间复杂度为 O(n\log n+q)，瓶颈在倍增。

:::success[AC code]

经过卡常后，时间花费仅有 156ms，峰值为 35ms。

下面是没有很卡常的代码，用时 173ms，峰值为 39ms。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
inline void write(int x)
{
    if(x>9)write(x/10);
    putchar(x%10+48);
}
const int N=100002;
int n,q,a[N],f[N][19],id[N][19],lg[N],ans;
inline void getl(int p,int q,int l,int r)
{
    if(l<1||a[p]>a[q])return;
    int s=lg[r-l+1],maxx,now;
    if(f[l][s]>f[r-(1<<s)+1][s])maxx=f[l][s],now=id[l][s];
    else maxx=f[r-(1<<s)+1][s],now=id[r-(1<<s)+1][s];
    if(maxx<a[p])ans+=r-l+1;
    else
    {
        if(maxx<a[q])ans+=now-l;
        int ls=lg[now-l],rs=lg[r-now],lmax=max(f[l][ls],f[now-(1<<ls)][ls]),
            rmax=max(f[now+1][rs],f[r-(1<<rs)+1][rs]);
        if(now==l)lmax=0;
        if(now==r)rmax=0;
        if(lmax>a[q]||rmax>a[q]||(lmax>rmax&&lmax>a[p]))return;
        ans++;
    }
}
inline void getr(int p,int q,int l,int r)
{
    if(r>n||a[p]>a[q])return;
    int s=lg[r-l+1],maxx,now;
    if(f[l][s]>f[r-(1<<s)+1][s])maxx=f[l][s],now=id[l][s];
    else maxx=f[r-(1<<s)+1][s],now=id[r-(1<<s)+1][s];
    if(maxx<a[p])ans+=r-l+1;
    else
    {
        if(maxx<a[q])ans+=r-now;
        int ls=lg[now-l],rs=lg[r-now],lmax=max(f[l][ls],f[now-(1<<ls)][ls]),
            rmax=max(f[now+1][rs],f[r-(1<<rs)+1][rs]);
        if(now==l)lmax=0;
        if(now==r)rmax=0;
        if(lmax>a[q]||rmax>a[q]||(rmax>lmax&&rmax>a[p]))return;
        ans++;
    }
}
signed main()
{
    n=read(),q=read(),a[0]=a[n+1]=n+1;
    for(int i=1;i<=n;i++)a[i]=f[i][0]=read(),id[i][0]=i;
    for(int i=2;i<=n;i++)lg[i]=-~lg[i>>1];
    for(int j=1;j<=17;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(f[i][j-1]>f[i+(1<<(j-1))][j-1])
                f[i][j]=f[i][j-1],id[i][j]=id[i][j-1];
            else f[i][j]=f[i+(1<<(j-1))][j-1],id[i][j]=id[i+(1<<(j-1))][j-1];
    for(int i=1,p,k;i<=q;i++)
    {
        p=read(),k=read(),ans=0;
        if(k==1)
        {
            puts("0");
            continue;
        }
        getl(p,p-k,p-k+1,p-1);
        getr(p,p+k,p+1,p+k-1);
        write(ans),putchar(10);
    }
    return 0;
}

:::

数据可以加强到 1\le n\le5\times10^5，1\le q\le10^7。