题解：P5978 [CEOI 2018] Global warming

xixisuper · 2025-11-11 12:53:39 · 题解

假设你要找一个区间加上 d>0，则这个区间一定是数列的后缀。

证明是简单的，因为假设某个位置 i 位于最终的答案中且 i 属于被操作的那个区间，则后面的数显然越大越好。

于是我们可以直接枚举所加的后缀是什么，假设是 [i,n]，则我们只需要考虑位置 i 在这个后缀中的最长上升子序列，并加上该位置的数放到前缀里所能得到的最长上升子序列。

求最长上升子序列的过程是 O(n\log n) 的，则总时间复杂度 O(n\log n)。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=2e5+10;
ll a[N],f_pre[N],g_pre[N],n,V;
ll f_suf[N],g_suf[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>V;for(ll i=1;i<=n;i++) cin>>a[i];
    ll tot=1;
    for(ll i=1;i<=n;i++){
        if(i==1) f_pre[i]=1,g_pre[1]=a[i];
        else{
            ll pos=lower_bound(g_pre+1,g_pre+1+tot,a[i]+V)-g_pre;
            f_pre[i]=pos;
            pos=lower_bound(g_pre+1,g_pre+1+tot,a[i])-g_pre;
            g_pre[pos]=a[i];
            if(pos>=tot) tot=pos;
        }
    }
    tot=1; 
    for(ll i=n;i>=1;i--){
        if(i==n) f_suf[i]=1,g_suf[1]=-a[i];
        else{
            ll pos=lower_bound(g_suf+1,g_suf+1+tot,-a[i])-g_suf;
            f_suf[i]=pos;
            g_suf[pos]=-a[i];
            if(pos>=tot) tot=pos;
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++) ans=max(ans,f_pre[i]+f_suf[i]-1);
    cout<<ans;
    return 0;
}