题解：P5978 [CEOI 2018] Global warming

假设你要找一个区间加上

d>0

，则这个区间一定是数列的后缀。

证明是简单的，因为假设某个位置

i

位于最终的答案中且

i

属于被操作的那个区间，则后面的数显然越大越好。

于是我们可以直接枚举所加的后缀是什么，假设是

[i,n]

，则我们只需要考虑位置

i

在这个后缀中的最长上升子序列，并加上该位置的数放到前缀里所能得到的最长上升子序列。

求最长上升子序列的过程是

O(n\log n)

的，则总时间复杂度

O(n\log n)

。

代码

CPP

#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;
}

题解：P5978 [CEOI 2018] Global warming

文章操作

代码

相关推荐

评论

题解：P5978 [CEOI 2018] Global warming