https://www.luogu.com.cn/problem/P4234
有基于 LCT 的 O(nlogn) 做法。

弱智 1log，被碾了

李超树合并 + dsu on tree

题解 https://www.luogu.com.cn/paste/3c4w30g1

题解 https://www.luogu.com.cn/paste/figzhd7q

duliu

biemozheng

新增两组hack数据，并hack了所有人
如果是这样的话前面的数据也可能有误？

第六七个点x有0？

回复 @湖岸与夜与咸�� :
你把块长和块数弄混了吧，值域1e6块长500应该有1e6/500=2000个块。
然后循环上下界有点问题，比如40行j=0，58行i>=1，60行j=sq-1，所以你WA了两个点。
至于第8个点，ai有好多负数，得修复

模拟水平太蒻了qwq

回复 @Skylake
是初中有一次把咱叫去听高中的课的时候讲的，当时我听完大受震撼，以至于其他题都忘了就记着这一题hh

回复 @Skylake :
我记得好早之前的集训讲过这题，没记错应该是不停按二进制分两组跑最短路，不过具体分法也忘了

回复 @Flyhouse :
《长度小于 r 且大于 l》
所有人赛时都这么写的，只有你的标算写的是“长度小于等于 r 且大于等于 l”，考虑赛时无法通知所有人只能改数据，不过现在你修一下题面也行

回复 @Skylake :
实际上线段树应该也是可行的，但是竟然没人写

@Skylake ，所以你写了个珂朵莉树?!

调了整整一晚上，属实给我整不会了

插件有问题，方案输出所有的行和列（即使大于答案次数）也能过

由于不会写插件舍弃了方案输出，并明确了朴素分数