感觉不是很显然啊,题解基本都是一笔带过 \fad;
具体来讲,题目要求可以看做:
- 区间统计 0 的数量
- 区间加减值(这里为 {1,−1});且保证任意时刻所有位置处值不大于 0
- 若有操作 [l,r,−1],保证在其之后对应地有操作 [l,r,1](以及操作 [l,r,1] 不能没有依赖地出现)
如果直接维护 0 的出现次数的话,区间减可以看做区间覆盖地打标记,但区间加就很难在打标记时维护 0 的个数
目前我只找到两种做法:
一种是注意到 3,因此可以把区间加看做撤销区间减的标记;同时为了避免标记不知道下传到哪,考虑直接永久化标记做
还有一种是注意到 “任意时刻所有位置处值不大于 0”;于是维护区间最大值和最大值出现次数,查询时检查下最大值即可
另外求问还有什么其它的做法吗qaq(甚至是适用更一般情况的做法)