关于这题的线段树部分
查看原帖
关于这题的线段树部分
105254
Piwry楼主2020/11/24 17:40

感觉不是很显然啊,题解基本都是一笔带过 \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(甚至是适用更一般情况的做法)

2020/11/24 17:40
加载中...