1 x y 把x改成y.
2 x y 询问区间[x,y]的mex.
part0 polylog做法
考虑整体二分,那就转换成了.
保留权值[vl,vr)的数,带修区间数颜色数(是否全部出现过 <=> 颜色数=vr-vl).
这个问题可以直接cdq.
复杂度O(n log^3 n).
part1
考虑分块不难做到.
O(1)单点修改(只往小了改).
O(sqrt n)寻找第一个小于k的位置.
具体来说直接分成根号块然后维护块内最小.
查询的时候用块内结果优化暴力跳即可.
part2
我们回顾一下这个问题不带修时经典的扫描线做法.
扫描线的时候维护一颗权值线段树,每个节点上记录权值v出现的位置中最靠右的,若不存在为-inf.
然后把询问挂在右端点上,从左向右扫描线,扫到的时候答案即为第一个<l的位置,线段树二分即可.
part3
考虑对操作分块,每sqrt n个操作分一块.
先把操作块内的修改作为添加操作加入.(修改应该是删除+添加,这里先不做删除处理).
构建出一个part1中所述的结构.显然可以线性.总体构建 O(sqrt n)次,这部分复杂度O(n sqrt n).
然后扫描线,询问挂在右端点上,从右向左扫描线.这里的操作只有删除,单次O(1).
扫到的时候,记录一个操作栈,然后把这个询问对应时间的删除全部加入.
接下来查询,单次复杂度O(sqrt n),查询O(n)次,复杂度O(n sqrt n).然后再用操作栈撤销删除,继续扫即可.
因为操作分块,单次询问加入的删除操作不超过O(sqrt n)次,复杂度O(n sqrt n).
总体复杂度O(n sqrt n).