FLOJ1302 [FR#113] 序列

题目链接

 

Solution

线段树。

每个节点维护区间,区间与,区间或,区间与异或上区间或就是区间中不确定的位置。

对于一个节点,如果询问中有用的每一位在该区间都确定了,就直接改,否则递归。

复杂度,一次操作会合并一整个区间,复杂度是,一次操作可以花费次操作的代价增加个区间。

所以复杂度是

 

Hints

在有些情况不好直接处理的时候,我们可以看一看什么状态是可以直接处理的。

然后在线段树上维护一些东西看这个节点是不是好处理的,再递归下去做。

分析复杂的的时候就根据询问算每次花费一个询问的代价造成的贡献,均摊一下。

注意压位的时候不要在外面每一位。。。。。

注意判断的时候不要忘了分与和或讨论一下

 

img

 

Code

 

跑的匪快。。。