扫描线整体二分（偏序整体二分）
P3242 [HNOI2015] 接水果
这是一道极好的神仙题，除了博弈论几乎没有任何其它题的思维有这题巧妙，其天才般的思想和知识点间美妙的融合让所有 OIer 叹为观止。确切地说，这是我此生见过的最巧妙的题，整体二分的实现也不由得让人对出题者产生由衷的钦佩。
注意到这居然是省选题。注意到我不知道风见幽香是谁。注意到这题居然是用盘子接水果而不是水果接盘子，盘子要被水果包含才能装住水果。
树上第 k 小，考虑整体二分，因为我们这篇的标题中整体二分排在最前面。假设我们的盘子是以下蓝色链条，x 和 y 是盘子的两个端点，z 是 x 在盘子上的儿子，能装住盘子的水果的两个端点为 u,v, 其中 depu<depvdep_u<dep_vdepu <depv （如果不是则将两个端点交换）, u 和 v 的最近公共祖先是 u：
此时图中红色的部分即是 u 可能的范围，蓝色的部分即是 v 可能的范围。
如果 u 不是 v 的祖先，则：
可贡献的图就如上所示了。因此，询问 (x,y)(x,y)(x,y) 与 lcau,v=u\operatorname{lca}_{u,v}=ulcau,v =u 时 stu∈[1,stz)∣(edz,N],stv∈[sty,edy]st_u\in [1,st_z)|(ed_z,N],st_v\in [st_y,ed_y]stu ∈[1,stz )∣(edz ,N],stv ∈[sty ,edy ] 和当不满足 lcau,v=u\operatorname{lca}_{u,v}=ulcau,v =u 时 stu∈[stx,edx],stv∈[sty,edy]st_u\in
[st_x,ed_x],st_v\in [st_y,ed_y]stu ∈[stx ,edx ],stv ∈[sty ,edy ] 的果子 (u,v)(u,v)(u,v) 有关。我们注意到这个约束条件很像是矩形，把每个盘子看作一个矩形，它能装住的所有点都是能接住的果子。问题转化为求一个点所在的所有矩形中第 kkk 小的权值，判断时将 [0,mid][0,mid][0,mid] 的所有矩形加一然后单点查询。可以在每次整体二分中排序，然后用扫描线求出被标记的数有多少个并进行二分。由于扫描线自带一次撤销操作，因此不用在整体二分后再清空树状数组。
这个扫描线没有面积并和周长并里的那么麻烦，只需要在扫到入边时加权，扫到出边时减回去（是个人都会做）。
Code：
成功拿到此题最优解：
