三维偏序,一维一维解决:第一维排序,第二维 CDQ ,第三维树状数组(或 CDQ )。

先按照 $a$ 进行排序,考虑 CDQ ,先分治左右两边,使得左右两边的节点都按 $b$ 排序,于是依次从两边取(优先 $b$ , $b$ 相等优先 $c$),左边的取出时在树状数组中更新,右边的取出时从树状数组中查询,考虑贡献。

需要注意的是,$a$ 、 $b$ 、 $c$ 的值都相同的节点有可能互相产生贡献,很难用 CDQ 解决,于是可以将这些点缩为一个,并单独计算他们内部互相产生的贡献。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×