【题解】P5978 [CEOI2018] Global warming

lnwhl · 2022-07-16 11:54:06 · 题解

目前的最优解。

Description

给定长度为 n 的数组 a ，你可以将任意一段区间 [l,r] 中的每一个元素 +d，其中 -x\le d\le x，问一次操作后的最长上升子序列长度。

Solution

如果将 [l,r] 区间内的元素都减小，可以增加 [l,r] 与 [r+1,n] 连接的 LIS 长度。但这有可能减小 [l,r] 与 [1,l-1] 这段的 LIS，所以我们可以贪心的想到，对于 d<0 的情况，选择 [1,r] 区间一定会比 [l,r] 区间更优。

对于 d>0 的情况也同理。因为区间内相对大小不变，所以不难发现将 [i+1,n] 加一个值的效果和 [1,i] 区间减一个值的效果是相同的，所以只需要考虑 d<0 的情况。

我们进一步分析，可以发现将 [1,i] 区间减的值越大一定更优。所以原问题就变成了求 [1,i] 区间内的元素都减去 x 后，最长上升子序列的长度最大为多少。

暴力修改 + LIS 的复杂度是 O(n^2\log n) 的，需要优化。考虑到修改过后区间内部相对大小不变，可以预先求出 [1,i] 区间以 a_i 结尾的 LIS 长度，为 L_i，设修改过后 [i,n] 区间以 a_i 开头的 LIS 长度为 R_i，答案即为 \max\limits_{i=1}^nL_i+R_i-1。复杂度是 O(n\log n) 的，轻松最优解。

当然，你也可以离散化后用树状数组求最大值，复杂度不变，只是代码复杂一些，欢迎读者思考。

Code

#include <bits/stdc++.h>
#define Rint register int
using namespace std;
const int N=2e5+5;
int n,x,a[N],lis[N],L[N],R[N],ans;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read(),x=read();
    for(Rint i=1;i<=n;++i)a[i]=read();
    memset(lis,0x7f,sizeof(lis));
    for(Rint i=1;i<=n;++i)
    {
        int j=lower_bound(lis,lis+n,a[i])-lis;
        lis[j]=a[i];L[i]=j+1;ans=max(ans,L[i]);
    }
    memset(lis,0x7f,sizeof(lis));
    for(Rint i=n;i>=1;--i)
    {
        int j=lower_bound(lis,lis+n,-a[i]+x)-lis;
        int jj=lower_bound(lis,lis+n,-a[i])-lis;
        lis[jj]=-a[i];ans=max(ans,L[i]+j);
    }
    printf("%d",ans);
    return 0;
}