社区讨论

关于这题的线段树部分

PPiwry
P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@locwoeu3
此快照首次捕获于
2023/10/30 20:58
2 年前
此快照最后确认于
2023/11/05 07:24
2 年前
查看原帖
感觉不是很显然啊，题解基本都是一笔带过 \fad；
具体来讲，题目要求可以看做：
  1. 区间统计 00 的数量
  2. 区间加减值（这里为 {1,−1}\{1, -1\}）；且保证任意时刻所有位置处值不大于 00
  3. 若有操作 [l,r,−1][l, r, -1]，保证在其之后对应地有操作 [l,r,1][l, r, 1]（以及操作 [l,r,1][l, r, 1] 不能没有依赖地出现）
如果直接维护 00 的出现次数的话，区间减可以看做区间覆盖地打标记，但区间加就很难在打标记时维护 00 的个数
目前我只找到两种做法：
一种是注意到 33，因此可以把区间加看做撤销区间减的标记；同时为了避免标记不知道下传到哪，考虑直接永久化标记做
还有一种是注意到 “任意时刻所有位置处值不大于 00”；于是维护区间最大值和最大值出现次数，查询时检查下最大值即可
另外求问还有什么其它的做法吗qaq（甚至是适用更一般情况的做法）

回复

共 2 条回复，欢迎继续交流。

正在加载回复...