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

本文写于2022-03-26 14:45:14。原博客地址

题目链接

算法

(倍增) $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;
}