引理：答案为 $2n-2-$ 凸包上的点数。

首先证明这是答案的下界。设最外层凸包点数为 $l_1$，把这些点去掉，对于剩下的点再求一次凸包得到第二层凸包点数 $l_2$……以此类推，我们可以把这些点划分成 $k$ 个相互包含的凸包，点数分别为 $l_1,l_2,\cdots,l_k$。

对于相邻两层凸包之间的部分进行三角剖分，可以得到 $l_i+l_{i+1}$ 个三角形，最里面的凸包直接三角剖分，因此总共有 $(l_1+l_2)+(l_2+l_3)+\cdots+(l_{k-1}+l_k)+(l_k-2)=2n-2-l_1$ 个三角形，这些三角形两两没有交，因此这是答案的下界。

其次，存在一个构造可以达到这个下界。

随机一个向量 $p$，使得任意两个蓝点构成的向量不与 $p$ 平行，令 $|p| \rightarrow 0$，同时在每个点 $+p$ 和 $-p$ 位置放两个点，可以证明这 $2n$ 个点满足要求。

这是因为把一个三角形的三个角平移到一起刚好可以覆盖 $180$ 度，根据抽屉原理必然有一个点落在这里。

但是 $2n$ 个点多了，我们把所有在凸包外面的红点删掉（注意凸包最两侧的点可以删掉 $2$ 个红点），因此剩余的总点数恰好为 $2n-2-$ 凸包点数。

证毕。

上述引理的证明过程也给出了构造。复杂度瓶颈在于 spj，是 $O(n^3 \cdot ans)$ 的。

Bonus：把 spj 的复杂度降为 $O(n^2(n+ans))$。

题解合集

引理：两人若都采取最优操作方案，那么 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)$。