两个序列任意选相同数量元素

标题应该叫什么。？

给定序列 $a=(a_1,a_2,...,a_n)$，$b=(b_1,b_2,...,b_m)$。

对于问题：从 $a$，$b$ 中分别选出 $k$ 个元素。

解决方案：考虑 $a$ 选了的和 $b$ 没选的元素加起来恰好 $m$ 个。

这样，$k$ 的具体值我们就不用关心了。

例 $1$：

多组询问，$1\le q\le10^6$，$1\le n\le m\le10^6$。

考虑上述思路，相当于从 $n+m$ 个物品中任意选 $m$ 个物品的方案数。

其中前 $n$ 个物品中当前选到表示原来的选到，后 $m$ 个物品中选到表示原来的没选到。

原式 $\displaystyle=\binom{n+m}{m}=(n+m)!(n!)^{-1}(m!)^{-1}$，预处理阶乘逆元即可。

例 $2$：

需要维护多重集合 $a$ 和 $b$：

$1$，在 $a$ 或 $b$ 中加入或删除一个元素 $x(-10^6\le x\le10^6)$；

$2$，在 $a$ 和 $b$ 中选择相同数量的元素，最小化选出元素之和并输出。

操作 $10^6$ 次。

先考虑正常做法。

维护一个权值线段树或树状数组，由于（排序后）选出的 $a$ 和 $b$ 单调递减，二分选择的元素数量 $k$ 使得 $a_k+b_k<0$ 即可。

因为在权值处维护，$a_k$ 和 $b_k$ 不在数据结构的同一位置。发现二分放不进去数据结构里，只能做到 $O(n\log^2{n})$。

考虑用上面的技巧。

$a$ 选的和 $b$ 不选的元素总数一定是 $b$ 的元素总数。

稍微转换一下，先钦定选了所有的 $b_i$，然后把 $a_i$ 和 $-b_i$ 放进线段树或树状数组。

想要找到桶中的前 $m$ 个之和，显然线段树或树状数组二分，时间复杂度 $O(n\log{n})$。

总结：以上面的为例，排列组合等价的东西实在是太多了，因此彻底明白本质是困难的，我们只需要找到一条路径就可以。