CF1446

CF1446D2 Frequency Problem (Hard Version)

给定一个长为 \(n\) 的序列 \(a\)，请你求出 \(a\) 中最长的连续段 \([l,r]\)，满足段内的众数不唯一。

\(n\le 2\times 10^5,\ a_i\le n\)

设整个序列的众数为 \(x\)，那么 \(x\) 也一定是段内的众数。否则考虑调整法：不断扩展区间，存在一个时刻 \(x\) 的出现次数会超过原本的众数，并且存在一个时刻二者出现次数相等，此时显然合法并且更优。

先考虑值域很小怎么做。我们可以枚举区间中的另一个众数 \(y\)，然后找到 \(x,y\) 出现次数相等的最长的区间。这里可以使用前缀和解决。

考虑原问题。对于数字的出现次数，考虑根号分治。仍然枚举另一个众数 \(y\)，若 \(y\) 的出现次数多于 \(\sqrt n\)，那么这样的 \(y\) 不超过 \(\sqrt n\) 个，直接 \(O(n)\) 暴力即可。若 \(y\) 的出现次数小于 \(\sqrt n\)，我们可以枚举连续段内众数的出现次数，然后用双指针对每个右端点求出最长的区间，再判断是否存在两个众数即可。时间复杂度 \(O(n\sqrt n)\)。

CF1446E Long Recovery

CF1446F Line Distance

给定平面上的 \(n\) 个点，它们两两之间连成了 \(\frac{n(n-1)}{2}\) 条直线，然后依次写出每条直线到原点的距离，问这些距离中的第 \(k\) 小是多少。

\(n\le 10^5,\ k\le \frac{n(n-1)}{2}\)

由于 \(k\) 高达 \(O(n^2)\)，因此不能枚举前 \(k\) 项。考虑二分答案，问题转换为：给定一个半径为 \(mid\)，圆心在原点的圆，求有多少条直线与圆相交。考虑如何判定一条直线是否与圆相交。

考虑圆外的两个点 \(A,B\) 和过它们的直线。作 \(A,B\) 向圆的四条切线 \(AP,AQ,BR,BS\)。发现直线 \(AB\) 与圆相交时，\(\overgroup{PQ}\) 和 \(\overgroup{RS}\) 要么无交，要么包含；其余情况两条弧在圆上交错。并且还有一个很好的性质：取一条弧在圆上的另一半，结果不变。

因此先求出 \(n\) 条弧，然后破环为链。对于经过断点的圆弧，我们将它替换为圆上的另一半即可。这样问题就转换到了序列上，我们需要统计有多少对区间是交叉的（有交但不包含）。这显然是一个二维数点问题。时间复杂度 \(O(n\log n\log V)\)。