P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

1.首先想到的做法

设up_len[i]为以a[i]为结尾的最长不下降子序列的长度，down_len[i]表示以a[i]为开始的最长不下降子序列的长度。

在求pre的过程中记录下额外信息：down_pre[i]表示在求down_len[i]的过程中，i是由哪个点转移过来的；

得到dp的转移方程：

if(down_pre[i])
            ans = max(ans, up_len[i] + down_len[down_pre[i]] + min(k, down_pre[i] - i - 1));
        else
            ans = max(ans, up_len[i] + min(k, n - i));

很好理解，这里采用了贪心

2.权值树状数组/权值线段树做法

参见这篇题解：

P8776 [蓝桥杯 2022 省 A] 最长不下降子序列 - 洛谷专栏 (luogu.com.cn)

！！！注意：

在最长不下降子序列中，

for (int i = 2; i <= n; i++)
    {
        if (a[i] >= en[res])
        {
            en[++res] = a[i];
            up_len[i] = res;
        }
        else
        {
            int pos = upper_bound(en + 1, en + res + 1, a[i]) - en;
            en[pos] = a[i];
            up_len[i] = pos;
        }
    }

这里应该是upper_bound而不是lower_bound，因为最长不下降子序列的en数组可能会有连续若干个值是相同的，如果采用lower_bound的话，那么修改其中一个，其他相等的也要同时做出修改；而upper_bound因为找到的值是唯一的，只需要单独修改这个点的值即可

完整代码：

1.二分dp做法：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <cmath>
#define R(x) x = read()
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 1e5 + 5;

int n, k;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int a[N], down_pre[N], up_len[N], down_len[N], en[N], id[N]; // id是反着做的辅助数组

int dp()
{
    // 正着做
    int res = 1, ans = -1;
    en[1] = a[1];
    up_len[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= en[res])
        {
            en[++res] = a[i];
            up_len[i] = res;
        }
        else
        {
            int pos = upper_bound(en + 1, en + res + 1, a[i]) - en;
            en[pos] = a[i];
            up_len[i] = pos;
        }
    }
    // for(int i = 1; i <= n; i++)
    //     cout << up_len[i] << " ";
    // 反着做
    res = 1;
    memset(en, 0, sizeof en);
    down_len[n] = 1;
    en[res] = -a[n];
    id[res] = n;
    for (int i = n - 1; i; i--)
    {
        int tmp = -a[i];
        if (tmp >= en[res])
        {
            down_pre[i] = id[res];
            en[++res] = tmp;
            id[res] = i;
            down_len[i] = res;
        }
        else
        {
            int pos = upper_bound(en + 1, en + res + 1, tmp) - en;
            en[pos] = tmp;
            id[pos] = i;
            down_len[i] = pos;
            down_pre[i] = id[pos - 1];
        }
        if(down_pre[i])
            ans = max(ans, up_len[i] + down_len[down_pre[i]] + min(k, down_pre[i] - i - 1));
        else
            ans = max(ans, up_len[i] + min(k, n - i));
    }
    /*for (int i = 1; i <= n; i++)
        cout << down_len[i] << " " << down_pre[i] << endl;*/
    ans = max(ans, up_len[n]);
    if(k >= n - 1)
        ans = n;
    return ans;
}

int main()
{
    R(n);
    R(k);
    for (int i = 1; i <= n; i++)
    {
        R(a[i]);
    }
    printf("%d\n", dp());
    return 0;
}

2.权值树状数组（需要离散化）：

这种做法也用到了一个贪心：即修改k个数字，一定比修改少于k个数字更优

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <cmath>
#define RT register
#define R(x) x = read()
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 1e5 + 5;

int n, k;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int a[N], down_pre[N], up_len[N], down_len[N], en[N], id[N]; // id是反着做的辅助数组

void dp()
{
    // 正着做
    int res = 1;
    en[1] = a[1];
    up_len[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= en[res])
        {
            en[++res] = a[i];
            up_len[i] = res;
        }
        else
        {
            int pos = lower_bound(en + 1, en + res + 1, a[i]) - en;
            en[pos] = a[i];
            up_len[i] = pos;
        }
    }
    // for(int i = 1; i <= n; i++)
    //     cout << up_len[i] << " ";
    //  反着做
    res = 1;
    memset(en, 0, sizeof en);
    down_len[n] = 1;
    en[res] = -a[n];
    id[res] = n;
    for (int i = n - 1; i; i--)
    {
        int tmp = -a[i];
        if (tmp >= en[res])
        {
            down_pre[i] = id[res];
            en[++res] = tmp;
            id[res] = i;
            down_len[i] = res;
        }
        else
        {
            int pos = lower_bound(en + 1, en + res + 1, tmp) - en;
            en[pos] = tmp;
            down_len[i] = pos;
            down_pre[i] = id[pos - 1];
        }
    }
    /*for (int i = 1; i <= n; i++)
        cout << down_len[i] << " " << down_pre[i] << endl;*/
}

int tr[N], b[N], cnt;

int lowbit(int x)
{
    return x & (-x);
}

int query(int x)
{
    int res = -1;
    while (x)
    {
        res = max(res, tr[x]);
        x -= lowbit(x);
    }
    return res;
}

void add(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] = max(tr[i], k);
}

int solve()
{
    memcpy(b, a, sizeof(a));
    sort(b + 1, b + n + 1);
    cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;

    for (RT int i = 1; i <= n; i++)
        up_len[i] = query(a[i]) + 1, add(a[i], up_len[i]);
    memset(tr, 0, sizeof(tr));
    for (RT int i = n; i >= 1; i--)
        down_len[i] = query(n - a[i] + 1) + 1, add(n - a[i] + 1, down_len[i]);

    memset(tr, 0, sizeof(tr));
    int ans = 0;
    a[n + 1] = cnt + 1;
    for (int i = k + 2; i <= n + 1; i++)
    {
        add(a[i - k - 1], up_len[i - k - 1]);
        ans = max(ans, query(a[i]) + k + down_len[i]); // 注意这两行：a[i-k-1]和a[i],要理解权值树状数组的含义
    }
    return ans;
}

int main()
{
    R(n);
    R(k);
    if (k >= n - 1)
    {
        printf("%d\n", n);
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        R(a[i]);
    }
    // dp();
    printf("%d\n", solve());
    return 0;
}