33OJ
登录 注册

#P17629. 永远的朋友

永远的朋友

背景

我还没问她在说什么,樽见就先抬起头。

「你这次要当我一辈子的朋友喔,小岛。」

樽见正在流泪。

是我害她流下了眼泪。

比冬天还要冰冷的某种东西降落在我的头顶上,穿过头发之间的空隙。

会因为维持朋友关系而哭,就表示──

脑袋一片混乱。

难道樽见也是吗?我本来想问她,喉咙却组织不出这句话。

「嗯。」

樽见用言语以外的方式传达的讯息,化成不多做停歇的风。这阵风跟河边的冰冷空气一同吹过我身上的细小空洞,留下轻微的疼痛。我的声音干燥到感觉不出任何水分。

这次要当我一辈子的──

朋友。

题目描述

岛村想要给安达准备一些手工品当作礼物。

商场里面有 nn 种材料,它们分别有一个特异值 a1,a2,…,ana_1,a_2,\ldots ,a_n。

她想要为安达准备 qq 个礼物,其中第 ii 个礼物用商城中编号在区间 [li,ri][l_i,r_i] 中的所有材料制成,这 (ri−li+1)(r_i-l_i+1) 份材料的特异值最初为 $[b_1,b_2,\cdots ,b_{r_i-l_i+1}]=[a_{l_i},a_{l_i+1},\cdots,a_{r_i}]$。

当然,她还要对材料进一步加工,以让礼物达到最完美的效果。准备第 ii 个礼物时,她用一个非负整数 sis_i 描述一个材料被加工后特异值的变化。具体来说,她可以对序列 bb 操作任意次,对于每次操作:

  • 选择一个整数 1≤p≤ri−li+11 \le p \le r_i-l_i+1,然后将 bpb_{p} 变为 (bpxor⁡si)(b_{p} \operatorname{xor} s_i)。

最后,她对礼物有两种评价标准:

  1. $\mathrm{K}_1=b_{1} \operatorname{and} b_{2} \operatorname{and} \ldots \operatorname{and} b_{r_i-l_i+1}$。
  2. $\mathrm{K}_2=b_{1} \operatorname{or} b_{2} \operatorname{or} \ldots \operatorname{or} b_{r_i-l_i+1}$。

她选择其中的第 TT 种,其中 T∈{1,2}T \in \{1,2\} 给定,她想要知道 KT\mathrm{K}_{T} 的可能达到的最大值。

她嫌这太麻烦了,你可以帮帮她吗?

其中 $\operatorname{xor},\operatorname{and},\operatorname{or}$ 分别表示按位异或、按位与、按位或三种位运算。

输入格式

第一行,一个数 TT,表示岛村选择的礼物评价标准。

第二行,两个数 nn 和 qq,分别表示商场的材料数量和礼物的数量。

第三行,nn 个数,依次表示商场材料的特异值 a1,a2,…,ana_1 ,a_2,\ldots ,a_n。

接下来 qq 行,对于其中的第 ii 行,有三个数,分别为 li,ri,sil_i,r_i,s_i,描述了第 ii 次询问。

输出格式

由于某些原因,你只需要输出 ∑i=1q(i×ansi)\sum_{i=1}^{q}(i\times \mathrm{ans}_i) 对 2642^{64} 取模的值。其中 ansi\mathrm{ans}_i 表示第 ii 次询问的答案。

1
5 5
21 32 56 21 53
1 3 21
2 4 54
3 5 4
1 5 23
2 4 1
209
2
5 5
21 32 56 21 53
1 3 21
2 4 54
3 5 4
1 5 23
2 4 1
927
1
5 5
184 799 161 254 543
1 3 4294967295
2 4 4294967295
3 5 4294967295
1 5 4294967295
2 4 4294967295
64424494912
2
5 5
184 799 161 254 543
1 3 4294967295
2 4 4294967295
3 5 4294967295
1 5 4294967295
2 4 4294967295
64424509425

提示

样例解释

对于样例一,每组询问答案分别为 16,32,20,16,116,32,20,16,1。

对于样例二,每组询问答案分别为 61,63,61,63,6161,63,61,63,61。


数据范围

本题目采用子任务捆绑测试。

对于所有数据:1≤n,q≤5×1051 \le n,q \le 5 \times 10^5,T∈{1,2}T \in \{1,2\}。

  • ∀1≤i≤n\forall 1 \le i \le n,有 0≤ai<2320 \le a_i<2^{32}。
  • ∀1≤j≤q\forall 1 \le j \le q,有 1≤lj≤rj≤n1 \le l_j \le r_j \le n,0≤sj<2320 \le s_j<2^{32}。

::cute-table{tuack} | 子任务编号 | n,q≤n,q\le | T=T= | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | 00 | 50005000 | 11 | 无 | 1010 | | 11 | ^ | 22 | ^ | ^ | | 22 | 2×1052 \times 10^5 | 11 | 有 | 2020 | | 33 | ^ | 22 | ^ | ^ | | 44 | 5×1055 \times 10^5 | 11 | 无 | ^ | | 55 | ^ | 22 | ^ | ^ |

特殊性质:∀1≤j≤q\forall 1 \le j \le q,有 sj=232−1s_j=2^{32}-1。


「我也好希望…… 自己有资格一起去很远的地方。」

我感觉有听见这样一段细语。

听起来就像河岸另一头的喧嚣一样遥远。

我想不到自己以前有做错什么决定,就这么随著名为现在的时间洪流前进。

我国中曾经跟人吵架。我曾经用言语伤害别人,让自己体会到尴尬的滋味。

但对方是我认为很讨人厌的家伙,连陌生人都不如。

所以,这想必是我第一次──弄哭了自己的朋友。