@SomeBottleLeetcode每日一题 —— 3161. 物块放置查询 中发帖

力扣我真得控制你了,这题挺有难度,看了题解才磨出来。 
综合考察了二分查找和常见线段树(单点修改、区间查询)。

思路
1. 新增与查询
题目中主要是两个操作,新增一个障碍物,或者查询一个障碍物左边最长的空闲区间是否 \ge sz。

每次 [1, x] 在 x 位置新增障碍物,都会把一段空闲区间切分为两段。
而每次 [2, x, sz] 进行查询时,我们只在意 [0, x] 区间中最大的空闲区间长度是否至少为 sz。

对于第 2 点,我们会进行多次的单点修改,而需要查询一个区间的最大值,因此可以用到常见的单点修改、区间查询线段树。
对于第 1 点,为了方便后续查询以及进一步的障碍物插入,我们每次插入肯定要知道 x 左边和右边的障碍物位置。这里就可以用有序集合来维护。
2. 线段树维护的内容
我们在查询的时候只在意某个位置 x 的左边最大的空闲区间长度,也就是说查询时希望能查...