【最长不下降子序列——树状数组、线段树、LIS】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], b[N], tr[N];//a保存权值，b保存索引,tr保存f，g前缀属性最大值
int f[N], g[N];
int n, m;
bool cmp(int x, int y)
{if(a[x] != a[y]) return a[x] < a[y]; //不下降，因此值递增return x < y; //不下降，允许重复，保留等于号（不保留是x > y，代表逆序，自然不成序列）
}
void modify(int x, int val)
{for(; x <= n; x += x & -x){tr[x] = max(tr[x], val);}
}
int query(int x)
{int retv = 0;for(; x; x -= x & -x){retv = max(retv, tr[x]);}return retv;
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i], b[i] = i;sort(b+1, b+n+1, cmp);int ans = 0, tmp;for(int i = 1; i <= n; i++){int p = b[i];f[p] = query(p-1) + 1;tmp = 0;if(p + m <= n) tmp = m;ans = max(ans, f[p] + tmp);modify(p, f[p]);}memset(tr, 0, sizeof tr);for(int i = n; i >= 1; i--){int p = n + 1 - b[i];g[b[i]] = query(p-1) + 1;tmp = 0;if(b[i] - m >= 1) tmp = m;ans = max(ans, tmp + g[b[i]]);modify(p, g[b[i]]);}memset(tr, 0, sizeof tr);for(int i = 1; i <= n; i++){int p = b[i];if(p > m+1) ans = max(ans, query(p - m - 2) + m + g[p]);modify(p, f[p]);}cout << ans;
}