AT_code_festival_china_j XORAND
题目描述
[problemUrl]: https://atcoder.jp/contests/code-festival-2014-china-open/tasks/code_festival_china_j
Yu 喜欢按位与运算和大数，Yu 的朋友 Yihuo 喜欢按位异或运算和小数。他们是好朋友，每当有人送他们一个整数数组作为礼物时，他们会一起分享这些数字。
对于一个非负整数数组 $p_1, p_2, ..., p_k$，令 $D$ 为数组所有数的按位与结果（$p_1$ AND $p_2$ AND ... AND $p_k$），令 $X$ 为数组所有数的按位异或结果（$p_1$ XOR $p_2$ XOR ... XOR $p_k$）。Yu 对 $p_1, p_2, ..., p_k$ 的满意度为 $D$，Yihuo 对同一数组的满意度为 $-X$（注意 Yihuo 喜欢小数，$X$ 越小他越满意）。
每当他们收到一个非负整数数组 $p_1, p_2, ..., p_k$ 作为礼物时，他们会把数组从中间某处切开，Yu 得到前半部分，Yihuo 得到后半部分。切割的位置是为了最大化两人各自满意度之和。更准确地说，他们会在 $1 \leq i < k$ 的某个 $i$ 之后切开，使得 Yu 对 $p_1, ..., p_i$ 的满意度与 Yihuo 对 $p_{i+1}, ..., p_k$ 的满意度之和最大。
现在给定一个长度为 $N$ 的非负整数数组 $A$ 和 $Q$ 个询问。第 $j$ 个询问问：“当我们把 $A_{l_j}, A_{l_j+1}, ..., A_{r_j}$ 送给 Yu 和 Yihuo 时，他们的满意度之和是多少？”你的任务是按顺序回答所有询问。
注意，每个询问由两个整数 $l_j, r_j$（$1 \leq l_j < r_j \leq N$）描述，但这两个整数并不是直接给出的。你需要根据上一个询问的答案计算出这两个整数，如输入部分所述。这意味着你必须按顺序计算每个询问的答案。
输入格式
第一行包含两个整数 $N$（$2 \leq N \leq 10^5$）、$Q$（$1 \leq Q \leq 10^5$），分别表示数组 $A$ 的元素个数和询问个数。
第二行包含 $N$ 个用空格分隔的整数。第 $i$ 个（$1 \leq i \leq N$）整数为 $A_i$（$0 \leq A_i < 2^{31}$）。
接下来的 $Q$ 行，每行包含两个整数 $l'_j$（$1 \leq l'_j \leq N$）、$r'_j$（$1 \leq r'_j \leq N$），表示第 $j$ 个询问的信息。
你需要根据下述方式计算每个询问的 $l_j$ 和 $r_j$：
- $l_1 = l'_1$，$r_1 = r'_1$
- 对于所有满足 $2 \leq j \leq Q$ 的 $j$，令 $m_{j-1}$ 为第 $j-1$ 个询问的答案。
- $l_j = ((l'_j + |m_{j-1}|) \bmod N) + 1$
- $r_j = ((r'_j + |m_{j-1}|) \bmod N) + 1$
注意，每个答案可能为负数，$|m_{j-1}|$ 表示 $m_{j-1}$ 的绝对值。保证 $1 \leq l_j < r_j \leq N$ 恒成立。
输出格式
输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 个询问的答案。输出末尾需换行。
说明/提示
### 题目说明
- 对于每个询问，你需要找到一个切割点，将区间 $A_{l_j}, ..., A_{r_j}$ 分为两部分，分别计算 Yu 和 Yihuo 的满意度之和，并输出最大值。
- $l_j$ 和 $r_j$ 的计算依赖于上一个询问的答案，必须按顺序处理所有询问。
### 样例解释 1
每个询问的答案如下：
- 第一个询问，$l_1 = 2$，$r_1 = 5$。区间 $3, 5, 4, 6$ 被分为 $3, 5$ 和 $4, 6$，Yu 的满意度为 $3$ AND $5 = 1$，Yihuo 的满意度为 $-(4$ XOR $6) = -2$，总和为 $-1$。
- 第二个询问，$l_2 = (2 + |-1|) \bmod 7 + 1 = 4$，$r_2 = (5 + |-1|) \bmod 7 + 1 = 7$。区间 $4, 6, 3, 1$ 被分为 $4, 6$ 和 $3, 1$，Yu 的满意度为 $4$ AND $6 = 4$，Yihuo 的满意度为 $-(3$ XOR $1) = -2$，总和为 $2$。
- 第三个询问，$l_3 = (3 + |2|) \bmod 7 + 1 = 6$，$r_3 = (4 + |2|) \bmod 7 + 1 = 7$。区间 $3, 1$ 只能分为 $3$ 和 $1$，Yu 的满意度为 $3$，Yihuo 的满意度为 $-1$，总和为 $2$。
- 第四个询问，$l_4 = (5 + |2|) \bmod 7 + 1 = 1$，$r_4 = (1 + |2|) \bmod 7 + 1 = 4$。区间 $7, 3, 5, 4$ 被分为 $7$ 和 $3, 5, 4$，Yu 的满意度为 $7$，Yihuo 的满意度为 $-(3$ XOR $5$ XOR $4) = -2$，总和为 $5$。
### 样例解释 2
每个询问的 $l_i, r_i$ 如下：
```
14 18
9 20
4 12
4 14
3 18
9 14
3 15
11 17
5 17
9 11
8 12
12 16
7 17
4 18
19 20
8 18
6 19
10 11
17 20
15 18
11 12
6 13
12 14
9 11
14 18
1 20
14 17
12 17
13 20
14 20
```
由 ChatGPT 4.1 翻译