1. 2027: [蓝桥杯2022初赛] 最长不下降子序列

传送门：http://oj.ecustacm.cn/problem.php?id=2027

1.1. 题意

给定数组$a$，可以修改连续的$K$个数字变成一个相同值。请计算修改后的最长不下降子序列长度。

1.2. Tag

动态规划、线段树

1.3. 难度

☆☆☆☆☆

1.4. 思路

最长不下降子序列是经典的动态规划问题。本题只和数字大小有关，与数值无关，因此，先对数组进行离散化。

记$dp[i]$表示以$a[i]$结尾的最长不下降子序列长度，对于修改连续的$K$个数字变成同一值，最好修改成与前面一样的数字，即：

修改$a[i-k+1],...,a[i]$均修改成$a[i-k]$，此时的最长上升子序列可以看成$3$段：

1. $[1,i-k]$：长度为$dp[i-k]$
2. $[i-k+1,...,i-1]$：长度为$k-1$
3. $[i,i+1...n]$：$a[i],a[i+1],...,a[n]$中，以$a[i]$开头的最长上升子序列，注意此时的$a[i]$的值应该等于$a[i-k]$

为了求出$dp[i]$，利用权值线段树求出$dp[1],...,dp[i-1]$中最大的数字$dp[j]$，同时保证$a[j]\le a[i]$。

具体做法为：对$a$数组离散化后，从左往右遍历$a$数组，将$a[i]$看作线段树的第$a[i]$位，$dp[i]$为线段树维护的值（线段树维护最大值），查询线段树区间$[1,a[i]]$的最大值即可。

类似的，反向遍历，每次查询$[a[i],n]$的最大值，就可以维护以$x$开头的最长上升子序列，这样，最后暴力枚举每一段$K$即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int a[maxn], b[maxn];
int dp[maxn];
///dp[i]表示以i结尾的最长上升子序列

///权值线段树，维护dp数组
int tree[maxn << 2];
void build(int o, int l, int r)
{
    tree[o] = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
}
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]);
}
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, tot = 0;
    read(n); read(k);
    for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];
    if(n == k)
    {
        cout<<n<<endl;
        return 0;
    }
    ///离散化
    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;

    build(1, 1, tot);
    int ans = 0;
    for(int i = 1; i <= n; i++)///从前往后遍历a，放入权值线段树中
    {
        ///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]
        dp[i] = query(1, 1, tot, 1, a[i]) + 1;
        update(1, 1, tot, a[i], dp[i]);
    }
    ///重新清空
    build(1, 1, tot);
    for(int i = n; i > k; i--)///从后往前遍历a，放入权值线段树中
    {
        ///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;
}