CEOI2018 Global warming 题解

· · 题解

P5978 [CEOI 2018] Global warming 题解

题目传送门

考虑对于一个区间加上或减去一个正整数会对整个序列的 LIS 产生怎样的影响。

假设我们对于区间 [l,r] 减去一个正整数，一个显然的结论是，区间 [l,r] 对 [r + 1,n] 造成的贡献会增加（或不变），而 [1,l - 1] 对 [l,r] 造成的贡献会减少。

因此如果想要对一个区间减少一个正整数值 x，我们希望尽量将 l 向前移动，因此如果选择对一个区间减去一个正整数，那么选择 [1,r] 一定是相对于 [l,r] 不劣的。

我们再来考虑对区间进行加法，使用同样的办法分析，不难发现，对于一个区间 [l,r] 加上 x 和对区间 [1,l - 1] 减去 x 是等价的，因此我们可以简化题意，也就变成了，我们可以对区间 [l,r] 减去一个值 x，求序列最长上升子序列长度。

还有一个需要分析的点是，减去的正整数值 x 应该更大还是更小，不难发现，x 的值更大显然是更优的，因此相当于我们需要对于一个 i，将区间 [1,i] 全部减 x，随后求序列最长上升子序列长度。

我们考虑如何去做这件事情，暴力修改并求 LIS 的时间复杂度是 O(n^2 \log n) 的，因此我们要考虑如何优化。

发现对区间 [1,i] 进行修改，对这段区间内的 LIS 是没有影响的，因此我们可以把序列拆为 [1,i] 和 [i + 1,n] 两部分，我们分别求出上升子序列长度，随后合并更新答案即可，时间复杂度 O(n \log n)。

贴代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;

int a[maxn];
int f[maxn],l[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ans = 0;
    memset(f,0x3f,sizeof(f));
    int n,x;
    cin >> n >> x;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++)
    {
        int nowx = lower_bound(f,f + n,a[i]) - f;
        f[nowx] = a[i];
        l[i] = nowx + 1;
        ans = max(ans,l[i]);
    }
    memset(f,0x3f,sizeof(f));
    for(int i = n;i >= 1;i--)
    {
        int nowx = lower_bound(f,f + n,-a[i] + x) - f;
        int nowl = lower_bound(f,f + n,-a[i]) - f;
        f[nowl] = -a[i];
        ans = max(ans,l[i] + nowx);
    }
    cout << ans << endl;
    return 0;
}