#C231116D. 最长不下降子序列(lis)

网址（Website）

题目详情 - 最长不下降子序列(lis) - Super

题解 - 最长不下降子序列(lis) - Super

题目（Problem）

大意：给出 $01$ 串，第一行为段数 $n$ ，接下来每行 $2$ 个整数 $a_i,b_i$， $a_i$ 表示当前段是 $0$ 还是 $1$ ，$b_i$ 表示个数，给定 $m$ ，表示询问数，对于每次操作：

区间翻转，翻转任意区间（$reverse$）；
输出翻转后能达到的最长不下降子序列长度；

注意：

输入：第一行一个整数 $n$，表示 $01$ 串的段数。接下来 $n$ 行每行两个整数 $a_i$，$b_i$。$a_i\in{0,1}$ 表示第 $i$ 段是全 $0$ 还是全 $1$，$b_i$ 表示第 $i$ 段的长度。保证 $\forall i\in[2,n]，a_i\ne a_{i-1}$ 。第 $n+2$ 行一个整数 $m$。
输出：共有 $m+1$ 行，输出翻转后能达到的最长不下降子序列长度，==其中第一行为原 $01$ 串的 $lis$ 长度==，后面 $m$ 行表示每次操作。

范围：$1\le n\le 2\times 10^5$；$0\le m\le n$；$a_i\in{0,1}$；$1\le b_i\le 10^9$ 。

题解（Solution）

$70pts$

对于一个 $lis$ ，找到一个位置 $i$ ，使 $[1,i-1]$ 中 $0$ 的个数与 $[i+1，n]$ 中 $1$ 的个数的加和有最大值。

考虑转化：先计算出所有的 $1$ 的个数，然后把 $0$ 的值设为 $1$ ， $1$ 的值设为 $-1$ ，原问题便转化为每次反转一个区间，求每次反转后最大的前缀和，即每次的最长不下降子序列为 $sum_{max}+tot_1$。（其中 $tot_1$ 代表 $1$ 的总数）

那么我们再来考虑每次翻转，很明显，如果当前的翻转取得了一个最优的 $ans$ ，对总体来说也是最优的，那么就可以用贪心的思想。怎么翻转才能使答案有最优解呢？

找到一个不在当前的 $ans$ 计算的区间里面的 $[l,r]\subseteq[1,n]$ ，将这个区间放在要计入的 $ans$ 里面，一定有正贡献；
替换一部分区间出来（要不然 $ans$ 的值不会被影响），这个区间不好寻找，但是我们知道，在该区间被替换出去以后， $ans$ 就变成了 $sum_z-sum_{y-1}+sum_{x-1}$ ，其中 $[y,z]$ 代表有最大正贡献的区间， $[x,y-1]$ 代表要被替换掉的区间。而当前的最大贡献区间已经求出来了，我们就只需要找到前面的最大的 $sum_{x-1}$ 就可以了。

对于每一次操作，倒着处理一遍，可以在 $O(n)$ 的时间内处理出来，总时间复杂度 $O(n^2)$ ，可以拿 $70pts$ 。注意，每次操作替换时后，一定要判断 $sum_z-sum_{y-1}+sum_{x-1}$ 是否大于 $ans$ ，如果小于，那么说明此时的 $a_i$ 数组已经有了最长的 $lis$ ，就没有翻转的必要了。

$100pts$

代码（Code）

70pts

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 201234;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n,m,a[N],sum[N],res;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	freopen("lis.in","r",stdin);
	freopen("lis.out","w",stdout);
	n=input();For(i,1,n){
		int x=input(),y=input();if(x) a[i]=-y,res+=y;
		else a[i]=y;
	}m=input();
	for(int i=1;i<=m+1;++i){
		int mx=0;for(int j=1;j<=n;j++) sum[j]=sum[j-1]+a[j],mx=max(mx,sum[j]);
		cout<<mx+res<<'\n';if(i==m+1) break;
		int l=1,r=1;
		int sy=-inf,y=0,sz=-inf,z=0;
		for(int j=n;j>=1;j--){
			if(sum[j]>sz) sz=sum[j],z=j;
			if(sz-sum[j-1]>sy) sy=sz-sum[j-1],y=z;
			if(sy+sum[j-1]>mx) mx=sy+sum[j-1],l=j,r=y;
		}reverse(a+l,a+r+1);
	}return 0;
}