简短线段树
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define mid (l+r>>1)
#define lson (root<<1)
#define rson (root<<1|1)
using namespace std;
const int maxn = 1e6 + 50;
int tree[maxn*4], a[maxn],n,l,f[maxn],g[maxn],k,ans=0;
void update(int root, int l, int r, int ll, int lr,int v) {
if (l > lr || r < ll) { return; }
if (l >= ll && r <= lr) { tree[root] = v;return; }
update(lson, l, mid, ll, lr, v);
update(rson, mid + 1, r, ll, lr, v);
tree[root] = max(tree[lson], tree[rson]);
}
int query(int root, int l, int r, int ll, int lr) {
if (l > lr || r < ll) { return 0; }
if (l >= ll && r <= lr) { return tree[root]; }
return max(query(lson, l, mid, ll, lr), query(rson, mid + 1, r, ll, lr));
}
int main()
{
cin >> n >> k;;
for (int i = 1;i <= n;i++) {
cin >> a[i];
f[i] = query(1, 1, 1e6, 1, a[i])+1;
update(1, 1, 1e6, a[i], a[i], f[i]);
}
memset(tree, 0, sizeof(tree));
for (int i = n+1;i >= 1;i--) {
g[i] = query(1, 1, 1e6, a[i], 1e6) + 1;
update(1, 1, 1e6, a[i], a[i], g[i]);
int pos = i - k - 1;
if (pos >= 1) { ans = max(ans, f[pos] + k + query(1, 1, 1e6, a[pos], 1e6)); }
}
cout << ans;
return 0;
}