【JZOJ4737】 金色丝线将瞬间一分为二

题目

思路

因为是曼哈顿距离，所以x,y可以分开考虑

法1

每个点考虑单独贡献。

x贡献：x∗比它小的数的个数−比它小的数的和+比它大的数的和−x∗比它大的数的个数$x\ast 比它小的数的个数-比它小的数的和+比它大的数的和-x\ast 比它大的数的个数$
y亦然。

用个splay维护一下?

时间复杂度O(nlogn)$O(nlogn)$

然而splay竟被卡常？？？

法2

splay常数大，换成树状数组吧。

然而x,y≤109$x,y\le {10}^9$怎么办？

快排离散化呗。

时间复杂度O(nlogn)$O(nlogn)$

法3

前面的方法太暴力了，动不动上数据结构。

注意这里是求临界条件，那我二分不行吗？

怎么O(n)$O(n)$求当前时间的距离和呢？

如果每次的x,y贡献都比前一个x,y要大就很好算吧。

但事实并非如此。

那我们就把x,y分开来，强行把它们分别排序再算。当前时间以后的点直接忽略掉就行了。

时间复杂度O(nlogn)$O(nlogn)$

总结

• 这种临界点问题既可以二分来做，也可以当成在线操作+查询这种数据结构题来做。
• 不过我还是更喜欢强推数据结构的啦ヾ(๑╹◡╹)ﾉ”