好题选讲02 - 洛谷保存站

# 好题选讲02
20231209-magic
## 题目描述
给定两个序列$a$，$b$，长度分别为$n$，$m$，每次操作挑选从未被计算过的$b_x$，将$a_i$替换成$b_x$，求最小的使$a$单调不降的操作次数,若无解，输出`-1`。

对所有数据:

令$c_x=\sum\limits_{i=1}^m[b_i=x]$即$b$序列中$b_i=x$的$i$的数量，保证$\forall x,c_x\le k$。

$1\le n,m\le400000,1\le k\le200,1\le a_i,b_i\le10^6$

|子任务编号|特殊限制|
|:--:|:--:|
|1|$1\le n,m\le1000$|
|2|$n\le1000,\forall i,j,a_i\neq b_j$|
|3|$\forall i,j,a_i\neq b_j$|
|4|$k\le10$|
|5|$k\le50$|
|6|$k\le200$|
## 题解
首先不妨将$b$数组排序，下文均以次为前提。

考虑第一个$sub$，有一个较为显然的$dp$，令$f_{i,j,0/1}$表示考虑到$a_i$，$b_j$，$a_i$是否被替换的操作次数，转移显然，复杂度$O(mn)$

发现特殊性质与$b$有关，考虑将$dp$下标中与$m$的部分去掉。考虑仅对$a_i$没有被替换的位置进行$dp$，即$f_i$表示考虑前$i$个数，且$a_i$没有被替换的最小操作数。

考虑转移，$f_j$能从$f_i$转移当且仅当存在至少$j-i-1$个$x$使得$a_i<b_x<a_j$（这里使用了特殊性质：$\forall a_i \neq b_j $，否则左右可能取等)，使用前缀和，$s_i$表示$b$中比$a_i$小的个数。可以进行$dp$，复杂度$O(n^2)$

考虑继续优化，$dp$能否转移要看$s_i-s_j\ge i-j-1$且$a_i\le a_j$，考虑加上$j<i$后三维偏序不好做，试图去掉一维。推式子，如果$j<i$且$s_i-s_j\ge i-j-1$，那么$i-j \ge 1$，于是$s_i-s_j\ge 1-1 =0$。根据定义，若$s_i>s_j$则$a_i>a_j$，当$s_i=s_j$时，$i-j\le 1$，又$i-g \ge 1$，此时$i-j=1$。对$i=j+1$进行特判，此时两维$dp$，使用数据结构优化，若$a_{i-1}<a_i$，先计算$f_i$再将$f_{i-1}$加入数据结构，反之，新加入再计算。复杂度$O(n\operatorname{log}n)$

接下来，考虑没有特殊性质，可能有$a_i=b_x$，考虑将$dp$扩展为二维，令$f_{i,j}$表示前$i$个数，$a_i$不变，使用了$j$个使得$b_x=a_i$的$b_x$，与上个算法较为类似，$f_{k,l}$能转移到$f_{i,j}$当且仅当$(s_i+j)-(s_k+l)\ge i-k-1$，即$i-s_i-j-1\ge k-s_k-l$，复杂度$O(nk\operatorname{log}n)$

继续优化，发现对于$f_{i,0}\sim f_{i,j}$，转移第二维$i-s_i-j-1$是一个区间，设其为$[l_i,r_i]$，发现$dp$时为后缀最大值，显然，$f_{i,l_i}\le f_{i,l_i+1}\le\cdots\le f_{i,r_i-1}\le f_{i,r_i} $，将数据结构维护的数组具象出来，不妨设为$d$，每次查询，由于后缀中每次只差一个数，先求$d_{r_i}$在数据结构中的后缀和，再逐个$O(1)$与$d_i$取$\operatorname{max}$，修改时，将$d_{l_i}$处的点值加到数据结构中，剩下只$O(1)$修改点值，正确性可以证明，复杂度$O(nk+n\operatorname{log}n)$

正在渲染内容...