关于一些新的由乃 OI
tmostnrq
简单题，直接对 a 扫描线，那要考虑加入一个关键点，把所有关键点进行一次移动，求某个关键点的位置。
对于向 x 移动的操作，只有 x 到根的链上面的点会往下移动，其他的点往上跳。对于关键点切换链的事件用平衡树和堆维护一下即可。注意要合并关键点，保证势能增加的点的数量为 O(log n)
写（没卡常的）fhq 跑了 5s，但其实可以用线段树维护，不好猜测 zky 写了什么。
hpi
今天才发现半平面莫队本身的构造是根号的（因为直接拿我袜子的代码 2e5 跑了 24s），惊讶。
就是随机撒关键点，然后对于某个半平面把他归附到最近的关键点上。对于每个关键点跑旋转扫描线，然后找到最近的关键点这一步要把两条平行线之间的点全部取出来。
这里我们在分块的时候把关键点也加进块里面，二分就省掉了。然后基数排序就能把所有的 log 去掉。
最后还要个树状数组维护逆序对，复杂度大概是 nsqrtnlogn 的，吧。预计今天内写一下。
完了，看错题了。
好像也一样，对于右上/左下的半平面就是直接数点，左上/右下的半平面可以容斥之后用树状数组维护。
lxl 声称这题标算是 nsqrtn 的。有点逆天。
草笑死我了，树状数组个锤子。平面分块就行。
2stmo
又是板子题。直接 top cluster 然后只用考虑簇路径上的点。相当于说，要 O(n^2) 地解决掉一棵规模为 n 的树上的两两点对。重剖，然后考虑一对点 (u,v) 从 (u,sonv) 和 (sonu,v) 中转移代价较小的转移过来。那么这棵树的代价大概就是 2*sum_{u,v} min(u的轻子树大小和,v的轻子树大小和)
画画说，轻子树大小和 >=2^k 的点有 O(n/2^k) 个然后就完了。一个经典的放缩方式。
不过贪心的构造 top cluster 好像理论上有 6 倍常数？上面的东西也带常数，需要进行逆天卡常。
pri
最不会的一题。之前问过 lxl 他们声称他们会 n^5/3，我不是很会去 log。
评价：再想想？
本题分为两个 part。
part1 我使用了 fhq 上底层分块+指令集实现，大概在 B=2^10 的时候跑了 2.5s，可以接受。
不过 part2 就必须无 log 了，这个我不是很懂。不过可以尝试实现一个带分裂合并的四分树。复杂度不知道。准备写一下。
运气比较好的话这东西就是正解的 n^2/3mlog^1/3
感觉那个不是很对。不如写个行分块然后 log^1/2
妈的我求两两块的顺序对就跑的巨慢，这玩意到底为啥跑得动啊？