作者:
炽热的
,
2022-10-21 18:04:03
,
所有人可见
,
阅读 105
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, k;
int a[N];
struct Fenwick {
int tr[M];
void add(int x, int k) {
for ( ; x < M; x += x & -x) tr[x] = max(tr[x], k);
}
int query(int x) {
int res = 0;
for ( ; x; x -= x & -x) res = max(res, tr[x]);
return res;
}
}f, g;
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
a[n + 1] = M;
int res = k;
for (int i = k + 2; i <= n + 1; i ++ ) {
g.add(a[i - k - 1], g.query(a[i - k - 1]) + 1);
f.add(a[i], f.query(a[i]) + 1);
f.add(a[i], g.query(a[i]) + 1);
res = max(res, f.query(a[i]) + k);
}
res = max(res, g.query(M - 1) + k);
printf("%d\n", res);
return 0;
}