CF425D Sereja and Squares 题解

很板的根号分治。对每一行内元素数量分治：

• 若某一行内元素数量 $\le \sqrt n$，则暴力枚举这一行内的两个元素，并用哈希表或类似的 ds 来判断这两个元素是否可以和上面一行或者下面一行的两点组成正方形。特殊的，若四个点所在行元素数量均 $\le \sqrt n$，则该情况会被计算两次，需要额外容斥。
• 若某一行内元素数量 $>\sqrt n$，则这样的行数目不会超过 $\sqrt n$，因此直接暴力枚举两个这样的行，然后枚举其中一行的任意一个顶点，判断是否存在一个这样的正方形即可。

总时间复杂度为 $O(n\sqrt n)$，可以通过该题。