最长不下降子序列

给定一个长度为 $N$ 的整数序列：$A_1,A_2, \ldots ,A_N$。

现在你有一次机会，将其中连续的 $K$ 个数修改成任意一个相同值。

请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。

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

输入格式

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

第二行包含 $N$ 个整数 $A_1,A_2, \ldots ,A_N$。

输出格式

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

数据范围

对于 $20\%$ 的评测用例，$1 \leq K \leq N \leq 100$；
对于 $30\%$ 的评测用例，$1 \leq K \leq N \leq 1000$；
对于 $50\%$ 的评测用例，$1 \leq K \leq N \leq 10000$；
对于所有评测用例，$1 \leq K \leq N \leq {10}^{5}$，$1 \leq A_i \leq {10}^{6}$。

输入样例：

5 1
1 4 2 8 5

输出样例：

4

解题思路

　　假设我们选取长度为$k$的区间$[l,r]$进行修改，然后在$[1,l-1]$中先选择一个不下降子序列，假设以$a_i$结尾，很明显为了使得不下降子序列最长，可以直接把$i \in [l,r]$内的数都修改成$a_i$。然后再从$j \in [r+1,n]$中找到一个以$a_j$开头的不下降子序列，其中要满足$a_j \geq a_i$，这样才能保证整个子序列是不下降的。

　　可以发现当固定了要修改的区间后整个序列被分成了前后两个部分，而现在要从这两部分中选择相应的$a_i$与$a_j$使得不下降子序列最长。由于我们需要用到以$a_i$为结尾的最长不下降子序列，和以$a_j$为开头的最长不下降子序列，因此要用线段树优化来求最长不下降子序列。

　　定义$f(i)$表示所有以第$i$个数结尾的不下降子序列中长度的最大值，$g(i)$表示所有以第$i$个数开头的不下降子序列中长度的最大值。状态转移方程就是$$f(i) = \max_{\begin{array}{center} 1 \leq j < i \\ a_j \leq a_i \end{array}} \left\{ f(j) \right\} + 1$$$$g(i) = \max_{\begin{array}{center} i < j \leq n \\ a_j \geq a_i \end{array}} \left\{ g(j) \right\} + 1$$

　　当然还需要用到权值线段树去优化，这样才能做到$O(n \log{M})$的时间复杂度，具体做法可以参考：线段树优化最长上升子序列问题。

　　考虑所有修改后的序列，我们可以把所有不下降子序列所构成的集合按照在前部分（假设修改区间为$[l,r]$，前部分指$[1,l-1]$）中不下降子序列以哪个数结尾来进行划分。因此可以划分的类别有：没有前部分，即修改的区间是$[1,k]$；以第$1$个数结尾；以第$2$个数结尾；一直到以第$n-k$个数结尾，即修改的区间是$[n-k+1,n]$。

　　对于以第$i$个数结尾的所有不下降子序列中，最大长度就是$f(i) + k + \max\limits_{\begin{array}{center} r < j \leq n \\ a_j \geq a_i \end{array}} \left\{ g(j) \right\}$，其中$r$是修改区间的右端点，取值范围是$r \in [i+k, n]$，这个修改区间可以是在$i$右部的任意一个长度为$k$的连续区间。首先$a_i$固定了，因此前部分最长的不下降子序列就是$f(i)$，然后再加上整个修改区间的长度，最后再加上在后部分满足开头至少为$a_i$的最长的不下降子序列。

　　对于没有前部分的情况，最大长度就是$k+ \max\limits_{k < j \leq n} \{ g(i) \}$。

　　因此我们可从右往左枚举修改区间的右端点$i$，开一个权值线段树来维护右部分的$g(i)$，这样就可以维护后缀最大值，查询右部分的最大值时直接在线段树中找到满足值大于等于$a_{i-m}$中最大的$g(i)$。

　　AC代码如下，时间复杂度为$O(n \log{M})$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 10, M = 1e6 + 10;
 5 
 6 int a[N];
 7 int f[N], g[N];
 8 struct Node {
 9     int l, r, maxv;
10 }tr[M * 4];
11 
12 void build(int u, int l, int r) {
13     if (l == r) {
14         tr[u] = {l, r, 0};
15     }
16     else {
17         int mid = l + r >> 1;
18         build(u << 1, l, mid);
19         build(u << 1 | 1, mid + 1, r);
20         tr[u] = {l, r, 0};
21     }
22 }
23 
24 void modify(int u, int x, int c) {
25     if (tr[u].l == tr[u].r) {
26         tr[u].maxv = c;
27     }
28     else {
29         if (x <= tr[u].l + tr[u].r >> 1) modify(u << 1, x, c);
30         else modify(u << 1 | 1, x, c);
31         tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
32     }
33 }
34 
35 int query(int u, int l, int r) {
36     if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
37     int mid = tr[u].l + tr[u].r >> 1, ret = 0;
38     if (l <= mid) ret = query(u << 1, l, r);
39     if (r >= mid + 1) ret = max(ret, query(u << 1 | 1, l, r));
40     return ret;
41 }
42 
43 int main() {
44     int n, m;
45     scanf("%d %d", &n, &m);
46     for (int i = 1; i <= n; i++) {
47         scanf("%d", a + i);
48     }
49     build(1, 1, M - 1);
50     for (int i = 1; i <= n; i++) {  // 求以a[i]结尾的最长不下降子序列
51         f[i] = query(1, 1, a[i]) + 1;
52         modify(1, a[i], f[i]);
53     }
54     build(1, 1, M - 1);
55     for (int i = n; i; i--) {   // 求以a[i]开头的最长不下降子序列
56         g[i] = query(1, a[i], M - 1) + 1;
57         modify(1, a[i], g[i]);
58     }
59     build(1, 1, M - 1);
60     int ret = 0;
61     for (int i = n; i >= m; i--) {
62         // 边界是i=m，此时修改的区间是[1~m]，对应不存在前部分的情况。而此时f[0]=a[0]=0，因此用同样的方法得到的结果也是正确的
63         ret = max(ret, f[i - m] + m + query(1, a[i - m], M - 1));
64         modify(1, a[i], g[i]);
65     }
66     printf("%d", ret);
67     
68     return 0;
69 }

参考资料

　　AcWing 4648. 最长不下降子序列：https://www.acwing.com/solution/content/143797/