题解合集

引理：两人若都采取最优操作方案，那么 Alice 的胜率等价于所有格子等概率随机颜色后，左边和右边连通的概率。

证明：

如果 Alice 在一个回合前知道 Bob 将会走哪个格子，那么假设他当前的策略也选这个格子，这样至少能够达到引理中胜利的概率，即所有格子颜色随机上下连通的概率。

同理，对于 Bob 来说也能够使用此策略达到“所有格子颜色随机左右连通的概率”的胜率。

因此考虑令 $x$ 为最终的期望得分，从 Alice 来看，$x \ge E($格子随机分配$)$，从 Bob 来看，$x \le E($格子随机分配$)$，因此 $x=E($格子随机分配$)$。

因此只需要计算所有格子颜色随机时，上下连通和左右连通的概率，插头 dp 即可。

先转曼哈顿，如果所有点的 $y=0$ 的话，那么任意一个匹配必然都经过 $x$ 的中位数（最大值的充要条件）。

取 $x$ 坐标的中位数 $a$ 和 $y$ 坐标的中位数 $b$ 得到点 $(a,b)$，然后以这个点为中心划分成一个十字，左上和右下匹配，左下和右上匹配即可。

假设 $n=2k$ 为偶数，那么左半边和右半边都有 $k$ 个，上半边和下半边也都有 $k$ 个。设左上有 $p$ 个，则右下有 $k-(k-p)=p$ 个，可以进行一一匹配；同理，左下也可以和右上进行一一匹配。

$n$ 为奇数时就记一下两维的前缀和，暴力计算出最优解应该删掉哪个点即可。复杂度瓶颈在 sort 上，$O(n \log n)$。

$type=0$ 是给莫队的，$m \le 10^5$ 是给按序列分块的（不过好像没卡掉）

做法 1

把区间排序，最后的答案必然在相邻两项中产生。不妨考虑值域分块，即按照值所在的范围把原序列划分为若干个子序列。

不妨令块大小为 $B$，经过这样的划分之后，一次询问必然能分成 $\frac{n}{B}$ 个区间，每个区间在对应的值域块内。

对于每个值域块，用区间 dp 预处理出答案，复杂度 $O(nB)$；对于跨块的情况，不难发现只需要计算某个区间最大值和最小值，st 表即可。

因此总复杂度 $O(nB+\frac{nm}{B})$，$B=\sqrt {nm}$ 最优，复杂度 $O(n\sqrt m)$。

做法 2

考虑从前向后扫统计以当前位置结尾，每个位置作为开头的答案。不妨假设大的元素必然是靠后的那个，考虑找到当前前缀中最大的、且比当前位置小的数字，它能够产生一个前缀的贡献；再找到最大数字到当前数字这个区间中最大的、且小于当前的数字……一个一个更新计算贡献即可，贡献大概是个区间 set，可以用线段树维护。

这样的做法会被卡到 $O(n^2logn)$，因此可以思考一下性质。假设当前元素为 $x$，找到的最大值为 $a$，$a$ 右边找到的最大值为 $b(b < a < x)$。如果 $b$ 和 $x$ 计算了贡献，那么 $b$ 必须满足 $a \ge \frac{x+b}{2}$ 才能进行更新，否则 $a,b$ 会产生更优的贡献。

因此总共只需要更新 $O(\log 10^9)$ 个元素，强制在线可以用主席树维护区间 set，总复杂度 $O(n\log n\log 10^9)$。

不难发现合法矩阵的充要条件是每条从右上到左下的斜线上，没有相邻两个颜色相同的格子。

（应该很好证，就不说了）

于是答案就是 $k^{n+m-1}(k-1)^{(n-1)(m-1)}$，快速幂即可。