题解

思路

设 $f_i$ 为以 $A_i$ 结尾的最长不下降子序列长度，$g_i$ 为以 $A_i$ 开始的最长不下降子序列长度。若修改段左右分别选择了下标 $i,j$，则必须有 $j-i-1\ge K$ 且 $A_i\le A_j$；把中间连续 $K$ 项改成介于二者之间的值后，可得到 $f_i+K+g_j$。还要考虑只选择修改段一侧的情形。

做法

$N\le100$ 时枚举修改段和修改值，再求 LNDS。$N\le1000$ 时二次 DP 求 $f,g$，并枚举左右端点。

完整算法对值离散化，用 Fenwick 树分别求 $f,g$。扫描右端点 $j$ 时，把恰好满足 $i\le j-K-1$ 的左端点加入另一棵 Fenwick 树，按值前缀查询所有 $A_i\le A_j$ 中最大的 $f_i$。同时单独计算只有左侧或只有右侧的答案。

复杂度

完整算法时间复杂度 $O(N\log N)$，空间复杂度 $O(N)$。

正确性证明

任意最优方案若同时选择修改段两侧元素，令 $i,j$ 为所选左右最近元素，则间隔至少容纳 $K$ 个被修改位置，且非下降性要求 $A_i\le x\le A_j$。左右部分最多分别贡献 $f_i,g_j$，故长度不超过转移值；反之取任意满足条件的 $i,j$ 并选取区间内的 $x$，该长度可以实现。只选择一侧的情况由边界转移覆盖，所以算法取到且不超过最优答案。