Description：

有 $n$ 个数，可以最多 $k$ 次把一个区间加一，求最后的最长不下降子序列长度。

$1\leqslant n\leqslant 10000,1\leqslant k\leqslant 500$

Solution：

首先既然求最长不下降子序列，那我们肯定要让靠后的尽量大，所以有一个重要性质是所有加一操作的右端点一定都是 $n$ ，那么我们可以设 $f[i][j]$ 表示最后一个选了 $i$ 号位置，一共进行了 $j$ 次加一操作的最长不下降子序列长度，转移为 $f[i][j]=\max(f[i][j],f[i'][j']+1)(i'<i,a[i']+j'\leqslant a[i]+j,j'\leqslant j)$ ，于是这就是一个三维偏序。显然可以 $CDQ$ 分治，但是会很麻烦，因为第一个符号是小于号而不是小于等于号，发现第一个和第三个限制都范围不大，可以直接二维树状数组。

排序一定要注意是双关键字的！最大值不一定在最后一个位置取得！

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 10010

int a[MAXN];

#define MAXK 510

struct query

{

	int i,j,x;

}q[MAXN * MAXK];

bool cmp_x(query a,query b){return (a.x != b.x ? a.x < b.x : (a.i != b.i ? a.i < b.i : a.j < b.j));}

int to(int i,int j){return (i - 1) * (k + 1) + j + 1;}

int f[MAXN][MAXK];

int lowbit(int x){return x & (-x);}

int c[MAXN][MAXK];

void add(int x,int y,int v)

{

	for(int i = x;i <= n;i += lowbit(i))

		for(int j = y + 1;j <= k + 1;j += lowbit(j))

			c[i][j] = max(c[i][j],v);

	return;

}

int calc(int x,int y)

{

	int res = 0;

	for(int i = x;i >= 1;i -= lowbit(i))

		for(int j = y + 1;j >= 1;j -= lowbit(j))

			res = max(res,c[i][j]);

	return res; 

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		for(int j = 0;j <= k;++j)

		{

			q[to(i,j)] = (query){i,j,a[i] + j};

		}

	}

	int tot = n * (k + 1);

	sort(q + 1,q + 1 + tot,cmp_x);

	for(int i = 1;i <= tot;++i)

	{

		f[q[i].i][q[i].j] = calc(q[i].i - 1,q[i].j) + 1;

		add(q[i].i,q[i].j,f[q[i].i][q[i].j]);

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans = max(ans,f[i][k]);

	}

	cout << ans << endl;

	return 0;

}