Statement
最长不下降子序列（LIS），但是有一次机会，让序列中连续 \(k\) 个数改成同一个数。\(n\le 10^5,a_i\le 10^6\).
Solution
记 \(f(i)\) 为以 \(i\) 结尾的 LIS 长度，\(g(i)\) 为以 \(i\) 开始的 LIS 长度，可预处理.
答案一定是 \(f(i) + k + g(j)\) 这样拼接起来的，其中 \(i+k+1\le j,a_i\le a_j\).
有人问我为什么？只需证“一定存在一种修改方式比不修改不劣”，考虑找出一个 LIS，然后在其中找一个数，把以他开头的 \(k\) 个数都修改为他，就一定不劣.
考虑把 \(i\) 从右往左移动，这时可选的 \(g(j)\) 数量每次增加 1，显然的考虑每次在 \(a_j\) 位置插入 \(g(j)\) 然后求 \([a_i..mx]\) 区间最大值，做完了.
\(O(n\log m)\)，\(m\) 为值域.
标签：le,不劣,题解,LIS,序列,P8776 From： https://www.cnblogs.com/laijinyi/p/18359233