「XSOI-R1」区间操作 (opt)

Luogu
IDLGP10401
Time2000ms
Memory128MB
DifficultyP3
洛谷原创O2优化枚举前缀和离线处理
小 A 给你了一个长度为 $n$ 的序列 $a$,并给你了 $q$ 组询问。 对于每组询问,小 A 会给你两个正整数 $l,r$,你需要求出 $(a_l) \oplus (a_l+a_{l+1}) \oplus (a_l+a_{l+1}+a_{l+2}) \oplus \dots \oplus (a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ 的值。 其中 $\oplus$ 表示异或运算。 ## Input 第一行两个正整数 $n,q$, 之后一行 $n$ 个整数 $a_i$, 之后 $q$ 行每行两个正整数 $l,r$。 ## Output 共 $q$ 行, 每行一个整数表示你的答案。 [samples] ## Background 小 A 喜欢区间操作问题。 ## Note **【样例解释 #1】** $1 \oplus (1 + 1) \oplus (1 + 1 + 4) \oplus (1 + 1 + 4 + 5) \oplus (1 + 1 + 4 + 5 + 1) \oplus (1 + 1 + 4 + 5 + 1 + 4) = 18$。 ### 数据规模与约定 **本题采用捆绑测试。** - Subtask 0(13 pts):保证 $n,q \le 10^2$。 - Subtask 1(28 pts):保证 $n,q \le 10^4$。 - Subtask 2(19 pts):保证 $a_i \le 10^4$。 - Subtask 3(7 pts):保证 $n \le 10^2$。 - Subtask 4(17 pts):保证 $a_i$ 均为 $2$ 的非负整数次幂。 - Subtask 5(16 pts):无特殊限制。 对于所有测试数据,$1 \le l \le r \le n \le 10^4$,$1 \le q \le 10^6$,$0 \le a_i \le 10^{10}$。 upd(2024.7.3):添加一组 hack 数据,减少一组数据。
Samples
Input #1
6 1
1 1 4 5 1 4
1 6
Output #1
18
Input #2
7 10
1 9 1 9 8 1 0
1 2
1 3
1 4
1 5
1 6
1 7
2 6
3 5
4 7
2 7
Output #2
11
0
20
8
21
8
23
25
24
11
API Response (JSON)
{
  "problem": {
    "name": "「XSOI-R1」区间操作 (opt)",
    "description": {
      "content": "小 A 给你了一个长度为 $n$ 的序列 $a$,并给你了 $q$ 组询问。 对于每组询问,小 A 会给你两个正整数 $l,r$,你需要求出 $(a_l) \\oplus (a_l+a_{l+1}) \\oplus (a_l+a_{l+1}+a_{l+2}) \\oplus \\dots \\oplus (a_l + a_{l+1} + a_{l+2} + \\dots + a_r)$ 的值。 其中 $\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10401"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 给你了一个长度为 $n$ 的序列 $a$,并给你了 $q$ 组询问。\n\n对于每组询问,小 A 会给你两个正整数 $l,r$,你需要求出 $(a_l) \\oplus (a_l+a_{l+1}) \\oplus (a_l+a_{l+1}+a_{l+2}) \\oplus \\dots \\oplus (a_l + a_{l+1} + a_{l+2} + \\dots + a_r)$ 的值。\n\n其中 $\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments