题解：DMY 3012 & 3016

· · 个人记录

3012

考虑最终无法继续消除的情况，存在于 2 \times 2 的黑色方块内的黑块一定无法消除。并且“伸出的斜线”也无法消除。如：

BBWWWWW BBBWWWW WWBBWWW WWWBBWW WWWWBBW WWWWWBB WWWWWBB

考虑伸出的斜线何时不被消除。分类讨论4种，以上图情况为例，在每条斜线上开平衡树，维护黑点、左边有黑点的黑点、存在于方块右上角黑点的黑点。单点修改，可以直接维护。查询就找左右端是否有满足条件的黑点就好了。

3016

首先思考怎么描述“是最大子段和”这个东西。

若左端点为 L ，考虑什么样的 R 满足条件。

------>>>>>>>>>

  1. 容易想到若L向左的后缀和若>0则一定可以向左扩，一定不优。所以L向左的所有后缀和<=0

  2. 同理可得，L向右到R的所有前缀和>=0

  3. 发现只剩不交的情况，记mss(R)为[R,n]的最大子段和。则 sum(L, R) >= mss(R)

（R同理。同时满足L和R的条件）

发现1对询问区间取交，是好描述的。2显然R在一段区间内。考虑3时，因为同时满足性质2（对称过来，R向左到L的所有后缀和>=0），得到sum(L, R)随R增大单调递增。mss(R)单调递减，所以也是一段区间。

怎么求呢？mss(R)可以预处理。应该只需要拆成两个sum，然后有查询区间最值工具st表，可能还要倍增。

至于题目中的询问，互相满足条件的点对，若抽象在二维平面上，就是两条横竖线有交点。然后就是数点，上线段树扫描线。