专栏文章
题解：DMY 3012 & 3016
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipv3wci
- 此快照首次捕获于
- 2025/12/03 18:26 3 个月前
- 此快照最后确认于
- 2025/12/03 18:26 3 个月前
3012
考虑最终无法继续消除的情况，存在于 的黑色方块内的黑块一定无法消除。并且“伸出的斜线”也无法消除。如：
考虑伸出的斜线何时不被消除。分类讨论4种，以上图情况为例，在每条斜线上开平衡树，维护黑点、左边有黑点的黑点、存在于方块右上角黑点的黑点。单点修改，可以直接维护。查询就找左右端是否有满足条件的黑点就好了。
3016
首先思考怎么描述“是最大子段和”这个东西。
若左端点为 ，考虑什么样的 满足条件。
------>>>>>>>>>
-
容易想到若L向左的后缀和若>0则一定可以向左扩，一定不优。所以L向左的所有后缀和<=0
-
同理可得，L向右到R的所有前缀和>=0
-
发现只剩不交的情况，记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表，可能还要倍增。
至于题目中的询问，互相满足条件的点对，若抽象在二维平面上，就是两条横竖线有交点。然后就是数点，上线段树扫描线。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...