时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是把小 S 和小 Y 变成 S 接 Y，仅此而已。

先进行一些分析。假设需要让 $(a,b,c)$ 分别是冠亚季军，那么：

1. $a$ 会尽量多过题且不会罚时；
2. $c$ 只会过一个题，且是最后一次提交才通过；
3. 除了这三个人之外的所有人都不过题。

更进一步的分析可以得到，$b$ 可行的过题情况有两类：

1. 在一次提交通过了唯一一个题，之前可能有罚时；
2. 过了两个题，最后两发提交才通过。

预处理出每个人作为冠军和季军的罚时，称为 $l_i,r_i$。只需要对于所有人作为亚军时的所有可行罚时情况，统计对应的 (冠军, 季军) 对的个数即可。

注意到，亚军过一个题且罚时大于 $L$ 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 $O(n\sqrt L)$ 的，具体地，可以 $O(c^2)$ 或 $O(c+L)$ 来统计可行罚时情况。

然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况，此时需要减掉。

查询需要减掉的情况数，本质是进行 $O(n \sqrt L)$ 次如下询问：对于 $[l,r]$，查询有多少 $i$ 满足 $[l_i,r_i]\subseteq [l,r]$。这是一个二维数点问题，可以离线下来做可持久化分块。更简单的做法是，容易发现，这 $O(n\sqrt L)$ 次询问中，只有 $O(n)$ 次询问的区间 $[l,r]$ 长度大于 $20$，所以可以提前预处理较短的区间的答案，对于较长的区间用主席树回答。

总时间复杂度是 $O(n\sqrt L + n\times 20^2 + n\log n)$。代码不是很难写，但是细节比较多。实现的时候不需要精细实现，复杂度多一点 $\log$ 或者 $20$ 也没卡。

关于 std：我偷看了一眼，看上去就没有根号分治，应该是 polylog 的。大概可以，每个人作为亚军时，每个提交对应了罚时情况中的一个公差为 $20$ 的等差数列，维护出区间之后大概处理一下，可以做到 $O(n\log n)$ 或者 $O(20\times n\log n)$。

IMO2023SL C1

将格子按照横纵坐标加和模 $3$ 分成等价类。每个等价类个数奇偶性需要相同，故可知 $3\mid nm$。

同时所有满足 $3\mid nm$ 的 $(n,m)$ 都合法。由 $3\times 2$ 和 $3\times 3$ 的构造显然得到，两个构造分别为：

00    11    11
00 -> 01 -> 11
00    00    11

和

000    011    011    011    101    111
000 -> 001 -> 101 -> 110 -> 100 -> 111
000    000    110    111    111    111

杜老师，我们喜欢你

我们喜欢你呀

我们喜欢你

阿皮阿杜老师，我们喜欢你

我们喜欢，插优第歪爱吃

先咕一下，闲下来写。

是我场上写的做法，只不过场上我以为它的复杂度是 $O(n \log n)$ 状物。

中间复杂度分析的部分有大量我的扯淡，请在看中间的分析之前先跳到最后查看正确的复杂度分析。

来写一下。

由于我不会 SMAWK，所以只能随机二分，自然询问次数为 $O(n\log n)$。

考察瓶颈所在的位置：二分提供 $O(\log n)$，双指针提供 $O(n)$。由于二分显然不可能被继续优化，考察如何减少双指针的次数。我的想法是设置步长 $s$，每一次指针移动的时候，相比于每次移动 $1$ 个位置，我们可以每次移动 $s$ 个位置。

这可能会带来误差，考察误差的影响。形象的思考带步长的双指针的过程。普通双指针实际上是找到了一个分割线/轮廓线，使得左上角是 $\leq mid$ 的数，右下角是 $> mid$ 的数。带步长的双指针找到的轮廓线是对这个轮廓线的一个粗略近似，但是它相比原轮廓线的误差不会超过步长 $s$。

那么我们二分再往两边递归的时候，如果想往左上递归，就将轮廓线往右下平移 $s$ 个位置，想往右下递归，就将轮廓线往左上平移 $s$ 个位置。这样所有当前可能成为第 $k$ 大的位置就仍然会被包含在待确定的区域中。

分析一下这个东西的询问次数。

我场上认为这个东西仍然是 $O(n\log n)$ 的，没有什么实质优化，所以一直在尝试调整步长 $s$ 并对拍。现在可以仔细分析一下询问次数了。下面的分析过程不太严谨，但是感性理解足够了。

设 $f(x)$ 表示当前待确定区域的左上到右下的斜向宽度（这里默认左下到右上方向的宽度为 $n$，显然不可能超过这个值）为 $x$ 的时候需要的询问次数。设步长为 $s$，有：

$$ f(x)=\min_{s} f\left(\frac{x}{2}+s\right)+O\left(\frac{n}{s}\right) $$

由于是随机二分，所以实际应该是一个概率分布，但是我正在感性理解，于是当成 $x/2$ 计算了。取 $s=\log x$，进行 $\log x$ 轮，由于 $s$ 远小于 $x$，暂时忽略这个 $f(x/2+s)$ 中的 $s$。那么有粗略的递推式：

$$ f(x)=f(\log x)+O(n) $$

然后大概就能得出 $f(n)=O(n\log^{*}n)$ 了。

虽然忽略 $s$ 这个事情看上去就不严谨，但是感性理解大概能得到一个这样的结果。然后这里不一定取到了下界，所以可能还会更优。

没有分析复杂度的常数，因为这东西本来就复杂度不优。并且我分析不明白，就这样。

感觉分析其实可能是错的，如果每一步都取 $s=\log x$，且忽略 $s$ 的话，只能得出：

$$ f(x)=f\left(\frac{x}{2}\right)+O\left(\frac{n}{\log x}\right) $$

然后这个解出来是 $f(x)=x\log \log x$。

请懂的人教我一下。@monstersqwq 教我一下谢谢。

其实是线性的，取 $s=x/2$，感谢咋克。

仔细分析各种乱七八糟的东西，最后可以得到 $15.5n$ 的复杂度上界。哈哈，没有任何意义。