P4344 [SHOI2015] 脑洞治疗仪
翻译题目
-
\(0\quad l\quad r\)：区间置 \(0\)。
-
\(1\quad l_0\quad r_0\quad l_1\quad r_1\)：将 \([l_0,r_0]\) 中的 \(1\) 取出，填到 \([l_1,r_1]\)（从左到右填入，多出去的扔掉）。
-
\(2\quad l\quad r\)，查询区间内最大连续 \(0\) 的长度。
思路
我们考虑维护类似于最大子段和的信息：(1)左边连续 0、(2)右边连续 0、(3)答案、(4)长度、(5)1 的个数。
为了方便，定义 \(l\) 表示左子树的区间，\(r\) 代表右子树的区间。
更新：
- 如果 \(l\) 有 \(1\)，那么肯定不可能穿透到 \(r\)，就是 \(l\) 的(1)；否则，\(l\) 的长度+ \(r\) 的(1)。
- 如果 \(r\) 有 \(1\)，那么肯定不可能穿透到 \(l\)，就是 \(r\) 的(2)；否则，\(r\) 的长度+ \(l\) 的(2)。
- l答案、r答案、l(2)+r(1)最大者。
- 不更新。
- 相加。
操作1：懒标记，直接更新。
操作2：二分找到可以填充的最右边的位置，然后操作1+区间置1。
操作3：询问若干个区间，然后像3一样合并答案，需要注意l(2),r(1)不能超出询问的区间边界。