UOJ Logo Universal Online Judge

UOJ

#431. 【集训队作业2018】time map

统计

7月28日,今天是阳光明媚的一天。

我提着行李,来到这座岛屿。一切都是如此的熟悉,是我实际上已经来过无数次了吗?

顺着弯弯曲曲的街道,我来到一座普普通通的民房。我知道,这里有我想见的人。

我曾经让她背负了太多太多。但直到失去,我才明白这一切。

我眼前飞过一只七彩的蝴蝶,它们的翅膀上散发着模糊的光芒。我是它们的一员吗?

屋里没有人。我打开房门,我看到地上有一本绘画日记。我打开它,一瞬间我想起了某人曾经说过的一句话:“这本日记是魔法的日记,在上面画的东西全都可以实现哦!”

我微微一笑,合上了日记。“umi,我等着你。”

给出一棵线段树,这个线段树是广义线段树。在正常的线段树中,对于区间$[l,r]$,我们会取$ m=⌊\frac{l+r}{2}⌋$,然后将这个区间分成 $[l,m]$ 和 $[m+1,r]$ 两个子区间。在广义的线段树中,$m$ 不要求恰好等于区间的中点,但是 $m$ 还是必须 满足 $l≤m< r$ 的。不难发现在广义的线段树中,树的深度可以达到 $O(n)$ 级别。

如下就是一棵广义线段树:

我们使用先序遍历给出该线段树每个节点的分界点,比如下列序列表示的就是该线段树:

5 1 3 2 4

表示的是$[1,6]$分界点为$5$,$[1,5]$的分界点为$1$,$[2,5]$的分界点为3等

已知这棵线段树的每个节点的值为他所代表的区间数的与。现在你需要支持如下操作:

1 l r x 表示将[l,r]的数都和x做与运算,并更新线段树
2 l r x 表示将[l,r]的数都和x做或运算,并更新线段树
3 l r x 表示将[l,r]的数都和x做异或运算,并更新线段树

保证$[l,r]$一定是线段树上某个节点代表的区间。

4 l r 询问从代表[l,r]的节点开始走,设当前节点的值为y,那么如果y在二进制下的表示中有奇数个1(即popcount(y)%2==1),向当前节点的左儿子走;否则向当前节点的右儿子走。走到不能走为止。输出经过的节点值的和

输入格式

第一行输入正整数$n,q$,表示这棵线段树维护的序列长为$n$,即该线段树有$2n-1$个点,有$q$个操作。

接下来输入$n$个正整数$a_i$表示这个序列的初始值

接下来输入这棵线段树

接下来$q$行,每行输入4个数或3个数,表示操作

输出格式

对于每个询问,输出答案

样例一

input

10 20
0 5 2 10 6 6 12 2 8 7
2 1 9 7 3 4 5 6 8
1 1 10 12
1 5 7 5
4 7 7
4 4 7
3 4 4 15
3 1 1 9
4 1 2
4 1 10
1 1 1 2
3 5 5 5
2 8 9 7
2 2 2 7
3 3 3 12
1 1 2 7
1 9 9 3
4 9 9
3 6 6 14
2 1 1 6
3 6 7 3
4 3 10

output

4
8
4
4
3
4

限制与约定

子任务1(10pts) $n,q\leq 10^3$

子任务2(20pts) $n,q\leq 10^5$,没有修改操作

子任务3(30pts) $n,q\leq 10^5$,没有异或操作

子任务4(40pts) $n\leq 10^6,q\leq 10^5$,无特殊性质

对于所有数据,$a_i,x\leq [0,10^9]$,保证给出的区间一定是线段树上某个节点所代表的。

时间限制:$4\mathtt{s}$

空间限制:$512\mathtt{MB}$

下载

样例数据下载