模拟赛 21 题解 | AlanSP's Blog

数论+计数+dp+贪心+堆

考虑到前缀 $gcd$ 值互不相同的只有 $O(\log n)$ 个，同时他们也是单调不升的。

所以我们可以暴力遍历所有的前缀 $gcd$ ，用双向链表删去那些与前面值相同的元素。

在删的时候注意把数量累加就好了。

~~差一点想出做法~~

首先，可以分位考虑，考虑每一位被统计了多少次。

我们知道，二进制中的一位被统计，当且仅当这一位在两个数中至少有一个 $1$ 。

我们可以统计出 $[0,n]$ 的数中这一位是 $1$ 的个数 $N$ ， $[0,m]$ 中的个数 $M$ 。

那么简单容斥一下，这一位的贡献就是 $Nm+Mn-NM$ ，我们重复计算了两位都是 $1$ 的部分。

问题传化为了求 $N$ ， $M$ 。

分类讨论一下：

好题。

首先将 $a$ 数组排序，有如下性质：

$a_i\leqslant b_i\leqslant a_{2n-i}$ ，根据中位数的定义显然。
任意 $i<j$ ，不存在 $b_{j}<b_i<b_{j+1}$ 或 $b_{j+1}<b_i<b_j$ ，考虑中位数每次向外拓展两个单位，不会一下比两个数都小。

根据这两条性质，我们可以进行 $dp$ 。

发现这些性质都是越向后越紧的，所以我们可以考虑从后向前 $dp$ ，维护哪些数可以成为中位数。

设 $f[i][j][k]$ 表示已经确定了 $[i,n]$ ，备选集合中 $<b_i$ 的数量为 $j$ ， $>b_i$ 的数量为 $k$ 的方案数。

考虑由 $i\rightarrow i-1$ ，增加的两个数 $a_{i-1}$ 和 $a_{m-i}$ （性质一），如果它们不等于 $a_i$ ，那么备选集合将扩大。

我们转移的决策就是在枚举 $b_{i-1}$ 选什么。

选了和 $b_i$ 相同的数：备选集合没有改变，直接 $f[i][j][k]\rightarrow f[i-1][x][y]$ 。
选了小于 $b_i$ 的数，那么就枚举这个数在集合中的排名 $l$ 。显然，排名在 $[l+1,i]$ 之间的都没有用（性质二），而 $b_{i}$ 因为比 $b_{i-1}$ 大，归到了后面那类： $f[i][j][k]\rightarrow f[i-1][l][y+1]$ 。
选了大于 $b_i$ 的数，同理： $f[i][j][k]\rightarrow f[i-1][l]$ 。

保证前面的合法，考虑新加两个位置的贡献。

为了保证合法，最后一个位置肯定是右括号，我们来讨论前面填什么。

所以开个小根堆，维护前面右括号中 $A-B$ 的最小值即可。