【最长不下降子序列——树状数组、线段树、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;
}