在同学们的努力下， 高匀感受到了 alb 的快乐。

高勺意犹未尽，找来了一个长度为 nn 的序列 a_1，a_2，….，a_na1​，a2​，….，an​ 。

她想要删除这个序列中的 kk 个数，然后将剩下的数按下标从小到大排列成一个长度为 n-kn−k 的序列 b_1，b_2，…，b_{n-k}b1​，b2​，…，bn−k​。

高勺定义她的快乐度为 bb 序列中满足 b_i=ibi​=i 的数量，即 \sum_{i=1}^{n-k} [b_i=i]∑i=1n−k​[bi​=i] 。

高勺想知道她的快乐度的最大值为多少。

第一行两个整数 n，k，n，k，表示序列的长度和删掉数的个数。

第二行 nn 个整数 a_iai​，表示杰哥的序列。

输出一个整数，表示 \sum_{i=1}^{n-k} [b_i=i]∑i=1n−k​[bi​=i] 的最大值

DP暴力的话可以得40~50分。考虑正解：

对于一个数ai+x=i，只有当他前面的数删去x过后才会产生1的贡献，我们将原数列按照数值递增，数值相等时位置递减排序，用c[x]维护删去x个数的最大贡献，加入一个数ax，他要产生贡献的话要删去x-ax个数，查询前缀的最大值并由此转移，我们需要一个单点修改和查询前缀max的数据结构，所以用树状数组。

1 #include
2 #define N 500005
3 #define fi first
4 #define se second
5 #define pi pair
6 //#define loveGsy
7 using namespace std;
8 int a[N], n, k, ans, c[N];
9 pair b[N];
10 void add(int x, int v) {
11 x++;
12 for (; x <= n; x += x & (-x)) c[x] = max(c[x], v); 13 } 14 int query(int x) { 15 x++; 16 int s = 0; 17 for (; x; x -= x & (-x)) s = max(s, c[x]); 18 return s; 19 } 20 void solve(int x) { 21 if (a[x] > x) return ;
22 int res = query(x - a[x]) + 1;//从前缀转移
23 add(x - a[x], res);
24 if (x - a[x] <= k && a[x] <= n - k) ans = max(ans, res); 25 } 26 bool cmp(pi a, pi b) { 27 return (a.fi ^ b.fi) ? a.fi < b.fi : a.se > b.se;
28 }
29 int main() {
30 #ifdef loveGsy
31 freopen("tree.in", "r", stdin);
32 freopen("tree.out", "w", stdout);
33 #endif
34 scanf("%d %d", &n, &k);
35 for (int i = 1; i <= n; i++) {
36 scanf("%d", a + i);
37 b[i] = make_pair(a[i], i);
38 }
39 sort(b + 1, b + n + 1, cmp);
40 for (int i = 1; i <= n; i++) solve(b[i].second);
41 printf("%d\n", ans);
42 return 0;
43 }