最长不下降子序列

问题描述

给定一个长度为 �N 的整数序列: �1,�2,⋯,��A1​,A2​,⋯,AN​ 。现在你有一次机会, 将其 中连续的 �K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数 列的最长不下降子序列最长, 请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列, 子序列中的每个数不小于在 它之前的数。

输入格式

输入第一行包含两个整数 �N 和 �K 。

第二行包含 �N 个整数 �1,�2,⋯,��A1​,A2​,⋯,AN​ 。

输出格式

输出一行包含一个整数表示答案。

样例输入

5 1
1 4 2 8 5

样例输出

4

最长的序列一定包含这k个数字，且k个数字连续

依次枚举每个位置，在k个数字之前，以第i个数字结尾的最长序列，之后以第i个数字开头的最长序列

权值线段树

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int a[maxn], b[maxn], dp[maxn];
//权值线段树，维护dp数组，不需要初始化
int tree[maxn << 2];
//更新下标为x，与val取max
void update(int o, int l, int r, int x, int val)
{
    if(l == r)
    {
        tree[o] = max(tree[o], val);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
//查询区间[L,R]最大值
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
        return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    if(n == k)
    {
        cout<<n<<endl;
        return 0;
    }
    //离散化
    int tot = n;
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - (b + 1);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;

    int ans = 0;
    //从前往后遍历a，放入权值线段树中
    for(int i = 1; i <= n; i++)
    {
        dp[i] = query(1, 1, tot, 1, a[i]) + 1;
        update(1, 1, tot, a[i], dp[i]);
    }
    //重新清空权值线段树
    memset(tree, 0, sizeof(tree));
    for(int i = n; i > k; i--)
    {
        //a[i-k+1] ... a[i]相等 均等于a[i-k]
        //最后一段要注意：查询的是[a[i-k],tot]中的最大值
        ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);
        int tmp = query(1, 1, tot, a[i], tot) + 1; //以a[i]开始的最长上升子序列长度
        ans = max(ans, tmp + k);
        //插入的是a[i]
        update(1, 1, tot, a[i], tmp);
    }
    cout<<ans<<endl;
    return 0;
}