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

前言（Front talk)

最长不下降序列的转换真的很妙！( •̀ ω •́ )✧

网址（Website）

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

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

题目（Problem）

大意：给出串，第一行为段数，接下来每行个整数，表示当前段是还是，表示个数，给定，表示询问数，对于每次操作：

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

注意：

输入：第一行一个整数，表示串的段数。接下来行每行两个整数，。表示第段是全还是全，表示第段的长度。保证 $，$ 。第行一个整数。
输出：共有行，输出翻转后能达到的最长不下降子序列长度，==其中第一行为原串的长度==，后面行表示每次操作。

范围：；；；。

题解（Solution）

对于一个，找到一个位置，使中的个数与 $，$ 中的个数的加和有最大值。

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

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

找到一个不在当前的计算的区间里面的，将这个区间放在要计入的里面，一定有正贡献；
替换一部分区间出来（要不然的值不会被影响），这个区间不好寻找，但是我们知道，在该区间被替换出去以后，就变成了，其中代表有最大正贡献的区间，代表要被替换掉的区间。而当前的最大贡献区间已经求出来了，我们就只需要找到前面的最大的就可以了。

对于每一次操作，倒着处理一遍，可以在的时间内处理出来，总时间复杂度，可以拿。注意，每次操作替换时后，一定要判断是否大于，如果小于，那么说明此时的数组已经有了最长的，就没有翻转的必要了。

代码（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;
}