题解 CF527C 【Glass Carving】

2018-12-20 09:38:36


这题有一点结论题的感觉。

首先你要发现,横着切与竖着切互相是没有影响的。

横着切成了很多段,显然此时面积最大的矩形的一边长就是这些段中长度最长的一段。

竖着切的也是一样的。

所以就可以用set/multiset来维护切过的横、纵坐标与每一段的长度。

修改时,先找到相邻的两刀,再找到对应的长度,删去这个长度,再加入切出来的两个新的长度。

一开始要把 $W$ 、 $H$ 这些东西加进去。

细节见代码

当然你不用set也行,手写平衡树就行了