题解

思路

按 $(A_i,B_i)$ 分类。

做法

00 位始终为 0，01 位只上翻一次，10 位只下翻一次；11 位要么始终为 1，要么先下翻再上翻。固定选择后，交换相邻的逆序操作可知：所有下翻应按 $C$ 降序进行，随后所有上翻按 $C$ 升序进行。若降序排列的下翻权值为 $d_1,\ldots,d_X$，降序排列的上翻权值为 $u_1,\ldots,u_Y$，始终保持为 1 的权值和为 $P$，总费用为 $\sum_{l=1}^X(l-1)d_l+\sum_{l=1}^Ylu_l+(X+Y)P$。交换两个 11 位的角色还能证明，保持为 1 的必定是这类权值中最小的若干个。

先令所有 11 位都临时归零，建立下翻、上翻两个多重集合及上述两个加权和；再按 $C$ 从小到大逐个把 11 位改为始终保持。删除一个权值时，用树状数组查询它在降序中的排名及其后所有元素的权值和，就能在 $O(\log N)$ 内更新加权和，同时维护保持权值和并取所有方案的最小值。

复杂度

总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。