动态规划题单4

91.[ARC114F] Permutation Division

Bob 的策略一定是按照开头从大到小排。
所以最后的答案一定不小于原来的排列。
所以我们要使得最后的排列 \(Q\) 和原排列 \(P\) 的 LCP 尽可能长。
也就是说最后分段的形式满足：(\(t_i\) 是每一段的开头)

• \(p_1=p_{t_1} > p_{t_2} > ... > p_{t_m}\)。
  不然的话，Bob 可以把后面的放到前面去。
  这些段就是 LCP 长度。
  
• \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k}  < p_{t_m}\)。
  此时 Bob 会把 \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k}\) 的 max 作为 \(q_{t_{m+1}}\)。
  

考虑二分 LCP 的长度 \(len\)，枚举 \(m\)，对于每个 \(m\) 我肯定是求出 \(p_{t_m}\) 的最大值，这样后面的段的选择会变多，设 \([len+1,n]\) 有 \(y\) 个数 < \(p_{t_m}\) 那么，如果 \(y+m\ge k\) 就是可行的，而 \(p_{t_{m+1}},p_{t_{m+2}},...,p_{t_k}\) 一定是选择最小的那几个。
于是问题变成求长度为 \(m\) 的下降子序列的末尾的最大值，这可以用 \(O(n\log n)\) 的 DP 来实现。
code

[code]#include#define PII pair#define fi first#define se second using namespace std;const int N=2e5+5;inline int read(){    int w = 1, s = 0;    char c = getchar();    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());    for (; c >= '0' && c