本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-30 08:11:16

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