题目背景
它的确很特殊,很引人注目,但异象从来都不特别。
它们终归只是错误而已:是人心里脆弱部分的回响,有着人心愿破碎时的音色。
就其本质而言,比起那颗心所渴望的,它们更接近那颗心本来的样子:一点也不特别, 但平凡同样可以拥有毁灭性的力量。
命运本身并不会带来缺陷,这样的痛苦也无法通过希望或命运的丝线挣脱——在这点上, 这枚曾经一度拥有摧毁性的强大力量的碎片能最终被找到并带回,和其他被寻得的碎片一样, 跟渴望没有一点关系。
大多时候,寻得异象的过程更像是追寻风的足迹,来无影去无踪,没有逻辑,也无需理由。
这片陈旧的,残缺的,容纳着悲伤和痛苦的躯壳…… 它能被找到,实在算不上什么奇迹,而仅仅是因为想要寻找它的人,心中都有着纯粹至极的情感,如此而已。 而这片连接起事物的存在,此时终于来到了她的唇齿之间。
题目描述
凡斯和德莱姆告诉彩梦,一个非负整数序列的 mex 为最小没有出现过的非负整数,例如 mex([0,1,3])=2。
彩梦定义一个非负整数序列的 xormex 为将每个元素异或一个相同非负整数后,序列 mex 的最大值,例如 xormex([8,9,11])=mex([8⊕9,9⊕9,11⊕9])=mex([1,0,2])=3。
给定长度为 2n 的序列 a 和 m 次询问,每次询问给定两个整数 l,r,彩梦想知道以下两个问题的答案:
- 子区间 [al,al+1,⋯,ar] 的 xormex。
- 对于所有 l≤x≤y≤r,子区间 [ax,ax+1,⋯,ay] 的 xormex 的和。
输入格式
第一行输入三个整数 n,m,o。
第二行输入 2n 个整数 ai。
接下来 m 行,每行输入两个整数 l,r。
输出格式
输出 m 行,每行包含一个整数,代表每个询问的答案。
如果 o=1,你需要输出第一个问题的答案。
如果 o=2,你需要输出第二个问题的答案。
样例 1
样例 1 输入
2 4 1
3 2 0 1
1 3
2 3
1 2
1 4
样例 1 输出
3
1
2
4
样例 2
样例 2 输入
3 5 2
0 4 6 7 5 2 1 3
1 8
3 5
2 6
3 7
1 4
样例 2 输出
93
9
29
22
15
附加样例 3~5
见下发文件的 desive3~5.in
与 desive3~5.ans
。
这些样例分别满足子任务 1,2,6 的限制。
样例解释
对于第一个询问,xormex([3,2,0])=mex([3⊕2,2⊕2,0⊕2])=mex([1,0,2])=3。
对于第二个询问,xormex([2,0])=mex([2,0])=1。
对于第三个询问,xormex([3,2])=mex([3⊕3,2⊕3])=mex([0,1])=2。
对于第四个询问,xormex([3,2,0,1])=mex([3,2,0,1])=4。
数据范围
对于所有数据,1≤n≤18,1≤m≤106,0≤ai<2n,1≤l≤r≤2n。
子任务编号 | n≤ | m≤ | o≤ | ai 两两不同 | 分值 |
---|---|---|---|---|---|
1 | 6 | 103 | 2 | 否 | 7 |
2 | 12 | 5×104 | 15 | ||
3 | 16 | 105 | 1 | 13 | |
4 | 17 | 5×105 | 16 | ||
5 | 18 | 106 | 10 | ||
6 | 17 | 5×105 | 2 | 是 | 12 |
7 | 18 | 106 | 5 | ||
8 | 17 | 5×105 | 否 | 14 | |
9 | 18 | 106 | 8 |
本题共 37 个测试点,子任务之间存在依赖关系,请不要频繁提交。
后记
将她从生与死的边界打捞的……是良方,还是奇迹?抑或是友谊?
……或许,都是吧。
当她的梦境第一回被光芒点亮的时候,她看见了她的朋友们为了保护她而奋不顾身的样子。 她确信,自己也会在它们遇见危险的时候这么做。 她一定会保护好它们——当然也包括她刚结识的那位新朋友。
当她们终于能彼此释怀,能够从容地分享自己所走过的路,讲述所遇到过的来自陌生人的善意的时候……
彩梦不禁笑了,她的嘴翘起了一个漂亮的弧度。 能自在释怀地笑,真是幸运至极呢。