题解 P8261【[CTS2022] 袜子】

whiteqwq · 2022-04-06 22:01:44 · 题解

P8261 [CTS2022] 袜子 解题报告：

更好的阅读体验

题意

给定 n 个带颜色的点，m 次查询 Ax_i+By_i+C<0,Ax_j+By_j+C<0,c_i=c_j 的点对 (i,j) 数量。

分析

显然题意可以转化为数一个点下方每种颜色直线数量平方和。

如果只数直线数量是等价于 #553. 【UNR #4】己酸集合 的，做法是：

对序列分块，然后每个块算出直线两两之间的交点，将交点和询问都按照 x 下标排序然后离线双指针，利用交点维护一下直线之间的顺序，这样询问就可以直接二分了。

令块长为 B，复杂度是 O(\frac{n}{B}(B^2\log B^2+q\log B)) 的。

那么考虑根号分治一下，每个大颜色集合都可以直接数直线数量然后平方。（块数还是 O(\frac{n}{B}) 的）

小颜色集合由于可以利用的性质是直线数量很少，所以我们可以很方便地维护小块直线之间的顺序。

我们考虑将贡献拆成被数到的直线数量，加上二倍被数到的直线在颜色中的 rk 之和，那么就可以类似地对直线交点和询问排序，每条直线在颜色中的 rk 可以很方便的维护，但是直线全局的 rk 不能直接维护。

由于每个颜色出现次数都 \leqslant B，很容易将所有颜色分成块长在 [B,2B) 内的块，其中每个颜色只在一个块内出现。

那么直接维护直线块内 rk 以及一个树状数组保存 rk 前缀和，询问枚举块直接二分查询即可。

复杂度还是 O(\frac{n}{B}(B^2\log B^2+q\log B))。

令 B=\sqrt q 就可以做到 O(n\sqrt q\log q+q\log q) 的复杂度了。

代码

咕了，有时间写。