【CF1437E】E. Make It Increasing（最长上升子序列好题）

题目链接：https://codeforces.com/problemset/problem/1437/E

简单地说，就是求被几个确定的数分成的每个区间内的最长上升子序列，我们可以对每个区间求一遍最长上升子序列。
题目中会有约束：区间的两边是已经确定的数。可以先去除已经在这两个数范围之外的数，因为这样的数是一定要进行操作来修改的。
那么如何求最长上升子序列呢，可以参考文章，时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
但是要将一个数列修改成严格单调是不能仅仅看最长上升子序列的，例如 [ 3 , 5 , 4 , 6 ] [3,5,4,6] [3,5,4,6]，最长上升为 [ 3 , 4 , 6 ] [3,4,6] [3,4,6]，但是不能仅仅通过修改 5 5 5来达到要求。也就是对于 1 ⩽ i < j ⩽ n 1leqslant i 代码

#include
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define MP make_pair

const int inf = 1e9 + 10;
const int N = 5e5 + 10;

int n,m;
int a[N], b[N];
vector v;

int cal(vector x)
{
	vector tmp;
	tmp.pb(x[0]);
	for(int i=1;i a[r])
		{
			flag = 0;
			break;
		}
		if(l + 1 == r) continue;
		v.clear();
		for(int i=l+1;i= a[l] && a[i] <= a[r]) v.pb(a[i]);
		ans += r - l - 1;
		if(v.size()) ans -= cal(v);
	}
	if(flag == 0) printf("-1n");
	else printf("%dn",ans);
	return 0;
}