线段树作为信息竞赛中最为常用的数据结构之一, 常常是区分非竞赛选手和竞赛选手的显著标志
其中最为有趣的就是有关区间可加性的探讨, 这里将会放一些我自认为可以学到东西的线段树题目,
同时也会附赠上自己的一些思考, 助读者加深对线段树的理解
Educational Codeforces Round 23: F.MEX Queries
线段树二分/懒标记线段树
解读:
本题本质就是实现区间赋值(全部赋值为0/1), 以及区间反转(区间异或1), 同时每一次操作之后都要找到第一个0的位置
难点1
因为是对于整个区间找到第一个0的位置, 那么很轻松就可以联想到线段树上二分, 但是我们要利用什么"信息" 进行二分呢?
常见的信息: 区间最值
例如我们要找第一个小于k 的位置, 那么可以对于当前区间[l, r]
- 查询
[l, m)的最小值是否是k, 如果是的话自然就可以从[l, m)向下递归 - 否则递归
[m, r)继续查找
这里可以看出线段树上二分其实是利用维护的"信息"进行"排除区间"的过程
回到本题, 我们试图利用区间最小值来实现找到第一个0, 这样可以找到吗? 当然可以, 但是却忽略了一个
重要的问题, 那么就是我们利用的"信息" 必须是可以维护的, 区间最小值无法在题目要求的反转操作下维护!
所以我们转而利用区间和 来找, 发现是可以的!(如果当前的区间和不等于区间长度, 那么说明这个区间有0)
难点2
我们想要设计懒标记来维护区间赋值, 那么自然地就可以这样设计
Tag= 1 -> 区间赋1
Tag= 0 -> 区间赋0
Tag= 2 -> 区间异或1
但是回归到我们老生常谈的话题, 解决懒标记下放问题, 重点就是解决懒标记相遇问题!
这里稍微分类讨论一下即可
难点3
这里操作区间范围是\(10^{18}\)
解决大区间问题我们就有两种选择, 动态开点线段树, 以及离散化后线段树
这里内存给的比较紧, 动态开点会MLE, 所以应该选择离散化 (如果大区间是\(10^9\) 的话 动态开点比较稳妥, 但是这里过大, 个人认为还是直接选择离散化为好)
但是我们最后要二分的是位置! 那么我们离散化中必须包含我们要二分的答案
这里分析一下, 发现我们的答案只可能是以下三种
- 最小的整数1, 比如我们一堆左右端点都很大的区间, 那么不管咋操作, 答案都是1
- 区间的左端点: 因为如果我们执行赋0操作, 假设答案在这个区间内, 那么肯定选择左端点更优
- 区间的右端点加1: 如果我们执行区间赋1操作, 假设区间左端点到1全部已经选上了, 那么最小的答案肯定是右端点加1
所以我们将这三类值, 加上区间左右端点一起进行离散化, 就完成了!