CF2205D Simons and Beating Peaks 题解

· · 题解

思路

解法一

考虑分治。从待处理区间 [l,r] 中取出最大值位置 mx，则以 mx 为最高点以外的删除操作仅能在 [l,mx),(mx,r] 中进行。因此可以进行分治。由于区间静态，可以使用 ST 表预处理出区间最大值。

定义 lcz(l,r) 为区间 [l,r] 的最小操作次数，则：

lcz(l,r)=\min(r-mx+lcz(l,mx-1),mx-l+lcz(mx+1,r))

效率为 O(n\log n)。

解法二

注意到最终序列应该是原序列的一个 \text{V} 字形子序列。例如样例：

1
7
1 3 2 4 6 5 7

最少操作 2 次得到 3 2 4 6 7。此时 2 是最低点（即最小值），2 左侧是一个原序列单调递减的子序列，右侧是一个原序列单调递增的子序列。

考虑枚举最低点位置，使用单调栈模拟删除操作，记位置 i 为最低点时，使左右侧合法的最小操作次数为 cl_i,cr_i。

具体来说，位置 i 成为最低点时，他需要删除自己左侧所有值小于自己的位置直到它遇到一个值大于自己的位置 j，将删除数量记作 l_i。同时它还要删除自己右侧所有值小于自己的位置直到遇到一个值大于自己的位置 k，删除数量记作 r_i。l_i,r_i 可以在单调栈出栈过程中维护，最终 cl_i=l_i+cl_j,cr_i=r_i+cr_k。

这个做法的效率是 O(n) 的。

总体来说，解法一相较于解法二思路更自然，但解法二理论效率高于解法一。

代码

:::info[解法一]

AC 记录

#include<bits/stdc++.h>
using namespace std;
const int NR=5e5+5;
int T;
int n;
int p[NR];
int f[NR][20],lg[NR];
int query(int l,int r){
    int k=lg[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int lcz(int l,int r){//递归求解
    if(r-l<=1) return 0;
    int mx=p[query(l,r)];
    return min(r-mx+lcz(l,mx-1),mx-l+lcz(mx+1,r));
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&f[i][0]);
        p[f[i][0]]=i;
    } 
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    printf("%d\n",lcz(1,n));
}
int main(){
    lg[1]=0;
    for(int i=2;i<NR;i++){
        lg[i]=lg[i>>1]+1;
    }
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

:::

:::info[解法二]

AC 记录

#include<bits/stdc++.h>
using namespace std;
const int NR=5e5+5;
int T;
int n;
int a[NR];
int l[NR],r[NR];//记录位置i左右各需删除多少
int cl[NR],cr[NR];//记录以i为最低点左右各需操作几次
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        l[i]=r[i]=0;
    }
    stack<int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.top()]<a[i]){
            l[i]+=l[st.top()]+1;
            st.pop();
        }
        cl[i]=l[i]+(st.empty()?0:cl[st.top()]);
        st.push(i);
    }
    st=stack<int>();
    for(int i=n;i>=1;i--){
        while(!st.empty()&&a[st.top()]<a[i]){
            r[i]+=r[st.top()]+1;
            st.pop();
        }
        cr[i]=r[i]+(st.empty()?0:cr[st.top()]);
        st.push(i);
    }
    int ans=2e9;
    for(int i=1;i<=n;i++){
        ans=min(ans,cl[i]+cr[i]);
    }
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

:::