#P14881. [OOI2022预选赛long]Битовый хаос位混沌

    ID: 14097 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-懒标记线段树标记复合奇偶性分析

[OOI2022预选赛long]Битовый хаос位混沌

题目描述

给定一个长度为 nn 的数组 aa。你需要处理以下几类操作:

  • upd and l r x:对所有 l≤i≤rl \le i \le r,执行 ai=ai&xa_i = a_i \& x;
  • upd or l r x:对所有 l≤i≤rl \le i \le r,执行 ai=ai∣xa_i = a_i | x;
  • upd xor l r x:对所有 l≤i≤rl \le i \le r,执行 ai=ai⊕xa_i = a_i \oplus x;
  • get and l r:求所有 l≤i≤rl \le i \le r 的 aia_i 的按位与;
  • get or l r:求所有 l≤i≤rl \le i \le r 的 aia_i 的按位或;
  • get xor l r:求所有 l≤i≤rl \le i \le r 的 aia_i 的按位异或。

其中 & 表示按位与,| 表示按位或,xor / ⊕\oplus 表示按位异或。

输入格式

第一行输入两个整数 n,qn,q,表示数组长度和操作数量。

第二行输入 nn 个整数:

a1,a2,ldots,an.a_1,a_2,\\ldots,a_n.

接下来 qq 行,每行按照题目描述中的格式给出一个操作。

输出格式

对于每个 get 操作,输出对应答案。保证每个测试中至少有一个 get 操作。

数据范围

对于所有测试数据:

1≤n,q≤500000,1 \le n,q \le 500000, 0≤ai≤1018,0 \le a_i \le 10^{18},

对于修改操作中的 xx:

0≤x≤1018,0 \le x \le 10^{18},

且:

1≤l≤r≤n.1 \le l \le r \le n.

样例

输入

10 10
5 7 3 10 12 0 11 15 14 31
get or 3 7
get xor 2 9
upd and 1 5 14
upd xor 3 10 7
get xor 1 10
get and 9 10
upd or 3 8 6
get xor 1 10
get or 5 5
get xor 4 6

输出

15
8
19
8
19
15
7

评分方式

测试点分为 9 组。注意,部分测试组不要求通过样例组。只有通过某一组的全部测试,并通过该组依赖的必要组,才能获得该组分数。

组别 分数 附加限制 必要组 说明
0 无 样例测试
1 11 n,q≤1000n,q \le 1000 0
2 无 只出现 upd xor 和 get xor
3 13 没有修改操作
4 12 只出现 upd and 和 get xor
5 q≤50000q \le 50000,数组值和修改值均不超过 10910^9 0
6 13 无 只出现 upd xor 和 get and
7 12 只出现与 and、or 有关的操作
8 n,q≤300000n,q \le 300000 0, 1
9 4 无 0–8