QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Total points: 100
[+19]
统计

题目背景

它的确很特殊,很引人注目,但异象从来都不特别。

它们终归只是错误而已:是人心里脆弱部分的回响,有着人心愿破碎时的音色。

就其本质而言,比起那颗心所渴望的,它们更接近那颗心本来的样子:一点也不特别, 但平凡同样可以拥有毁灭性的力量。

命运本身并不会带来缺陷,这样的痛苦也无法通过希望或命运的丝线挣脱——在这点上, 这枚曾经一度拥有摧毁性的强大力量的碎片能最终被找到并带回,和其他被寻得的碎片一样, 跟渴望没有一点关系。

大多时候,寻得异象的过程更像是追寻风的足迹,来无影去无踪,没有逻辑,也无需理由。

这片陈旧的,残缺的,容纳着悲伤和痛苦的躯壳…… 它能被找到,实在算不上什么奇迹,而仅仅是因为想要寻找它的人,心中都有着纯粹至极的情感,如此而已。 而这片连接起事物的存在,此时终于来到了她的唇齿之间。

题目描述

凡斯和德莱姆告诉彩梦,一个非负整数序列的 mex 为最小没有出现过的非负整数,例如 mex([0,1,3])=2

彩梦定义一个非负整数序列的 xormex 为将每个元素异或一个相同非负整数后,序列 mex 的最大值,例如 xormex([8,9,11])=mex([89,99,119])=mex([1,0,2])=3

给定长度为 2n 的序列 am 次询问,每次询问给定两个整数 l,r,彩梦想知道以下两个问题的答案:

  • 子区间 [al,al+1,,ar]xormex
  • 对于所有 lxyr,子区间 [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.indesive3~5.ans

这些样例分别满足子任务 1,2,6 的限制。

样例解释

对于第一个询问,xormex([3,2,0])=mex([32,22,02])=mex([1,0,2])=3

对于第二个询问,xormex([2,0])=mex([2,0])=1

对于第三个询问,xormex([3,2])=mex([33,23])=mex([0,1])=2

对于第四个询问,xormex([3,2,0,1])=mex([3,2,0,1])=4

数据范围

对于所有数据,1n181m1060ai<2n1lr2n

子任务编号 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 个测试点,子任务之间存在依赖关系,请不要频繁提交。

后记

将她从生与死的边界打捞的……是良方,还是奇迹?抑或是友谊?

……或许,都是吧。

当她的梦境第一回被光芒点亮的时候,她看见了她的朋友们为了保护她而奋不顾身的样子。 她确信,自己也会在它们遇见危险的时候这么做。 她一定会保护好它们——当然也包括她刚结识的那位新朋友。

当她们终于能彼此释怀,能够从容地分享自己所走过的路,讲述所遇到过的来自陌生人的善意的时候……

彩梦不禁笑了,她的嘴翘起了一个漂亮的弧度。 能自在释怀地笑,真是幸运至极呢。