题解：P11370 [Ynoi2024] 堕天作战/虚空处刑
也许更烂的阅读体验：my blog
不是我想写的，是 lxl 老师布置的题单里有。
仿照 P3316 的思路，我们将多边形的每一条边按横坐标分拆到
不过现在我们就需要讨论两种情况，一种是查询所在结点在修改（指初始的多边形的边）下方，
我们在所有查询结点在线段树上所有的祖先结点进行操作。
这样修改形成若干贯穿区间的直线,查询形成线段。
根据修改直线形成一个多边形，我们可以得知这些直线是不交的（至多交于端点）。
查询的时候便可以直接二分得到线段两个端点的 rank，比较是否相等就好了。（判掉端点与直线相交）
另一种则是在下方。
这样的话多边形的边形成若干“牙齿”与“耳朵”：
(很像吧)
对于那些牙齿（也就是与区间左右端点相交的连通块），一条线段显然至多只会与它的前驱后继相交。
所以我们对每个牙齿求一个凸包，查询的线段（实质上现在是直线）在凸包上二分就好了。
重点是耳朵。
首先特判这种情况：
这个东西按耳朵与左半区间（右耳朵同理）的交排序之后二分就好了。
然后有一个误区是直线也至多与前驱后继的耳朵相交，但这是不对的。
按左上作为例子，我们需要加入直线左上方的所有耳朵，并将它们的端点求个凸包就好了。这个过程可以离线之后扫描线解决。
合并凸包的时候比较麻烦，但其实我们只用维护凸壳，这个过程用双指针做，细细讨论就好了。
需要对四个方向分别做一遍。
最后有一个小问题，就是查询与修改都垂直于
没错这道题就是这样，思维难度不算高，但是代码确实难（也许想清楚了可以很快写完？）。
仿照 UOB 放代码：
代码
有若干样例在我的博客里，当然自己拍才是最好的。
我声称我找到了一种很好的卡常方式（当然可能没用），如果你真的被卡常了可以私信我。