P8251 [NOI Online 2022 提高组] 丹钓战 题解

· · 题解

算法

(倍增) O((n+q) \log n)

为简便，把元素 (a_i,b_i) 称为元素 i。

对一个区间 [l,r] 模拟一遍，从空栈开始，头一个元素是“成功的”，然后堵在栈底直到被弹出，这期间入栈的元素不可能是“成功的”，弹出后栈又被清空，又回到了开头情况。所以答案就是整个过程中栈底元素的个数。因为任意元素只会被唯一元素弹出一次，所以可以从 1 到 n 模拟一遍，记 s_i 会被 s_{nxt_i} 弹出，复杂度为 O(n) 。

求解过程转化成代码为：

int ans=1;  //首次入栈元素是“成功的”
for(int p=l;p<=r;p=nxt[p])  ans++;

可如果询问区间内每个 nxt_i 都指向 nxt_{i+1}，那么相当于一步一弹，和暴力模拟没有区别。 定义 f_{i,j} 为从元素 i 开始弹 2^j次后的元素。若没有则为 0。在 f 上面转移，一步弹2的幂次元素，就把询问优化到了 O(\log n)。f 的预处理复杂度为 O(n \log n)。

思想：倍增。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
//支持负数
template<typename T>
inline void read(T &x)
{
    char ch;bool flag = 0;
    while(!isdigit(ch=getchar()))
        (ch=='-')&&(flag=true);
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
    (flag)&&(x=-x);
}
template<typename T>
void print(T x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

typedef long long ll;
const int N=5e5+10,K=20;
int n,m,a[N],b[N],stk[N],tt,f[N][K];
inline bool check(int x,int y){return a[x]!=a[y]&&b[x]<b[y];}

int main()
{
    // freopen("stack.in","r",stdin);
    // freopen("stack.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=n;i++)   read(a[i]);
    for(int i=1;i<=n;i++)   read(b[i]);

    /init
    for(int i=1,tt=0;i<=n;i++)  //模拟，预处理f[i][0]
    {
        while(tt&&!check(i,stk[tt]))
            f[stk[tt--]][0]=i;
        stk[++tt]=i;
    }
    //元素i弹2^j次后的元素当然是
    //它弹2^(j-1)次后再弹2^(j-1)次后的元素
    for(int k=1;k<K;k++)    //从后往前转移f
        for(int i=n;i>=1;i--)
            f[i][k]=f[f[i][k-1]][k-1];

    //work
    for(int i=1,l,r;i<=m;i++)
    {
        read(l),read(r);int res=1; 
        for(int k=K-1;k>=0;k--)
            if(f[l][k]<=r&&f[l][k]) //注意要判f[l][k]!=0
            {
                res+=1<<k;
                l=f[l][k];  //一步弹2^k次
            }
        print(res),putchar('\n');
    }
    return 0;
}