D. [R15D]二维异或和

    Type: Default 1000ms 512MiB

[R15D]二维异或和

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

给定一个长度为 nn 的整数数组 AA

定义区间 [L,R][L,R] 的二维异或和为 i=LRj=LRAiAj\sum_{i=L}^R\sum_{j=L}^R A_i\oplus A_j,这里的 \oplus 表示按位异或运算。

qq 个询问,第 ii 个询问求区间 [Li,Ri][L_i,R_i] 的二维异或和。

格式

输入格式

第一行包含两个整数 n,qn,q,分别表示数组 AA 的长度和询问的数量。

第二行包含 nn 个整数 AiA_i

接下来 qq 行每行两个整数 Li,RiL_i,R_i,表示第 ii 个询问。

输出格式

输出 qq 个整数,第 ii 个整数表示第 ii 个询问的答案。

样例

样例输入 #1

5 3
1 3 2 7 6
1 3
3 4
5 5

样例输出 #1

12 10 0

样例解释 #1

11 个询问的答案为 $(1\oplus 1)+(1\oplus 3)+(1\oplus 2)+(3\oplus 1)+(3\oplus 3)+(3\oplus 2)+(2\oplus 1)+(2\oplus 3)+(2\oplus 2)=0+2+3+2+0+1+3+1+0=12$。

22 个询问的答案为 $(2\oplus 2)+(2\oplus 7)+(7\oplus 2)+(7\oplus 7)=0+5+5+0=10$。

33 个询问的答案为 66=06\oplus 6=0

数据规模

对于 20%20\% 的数据,n300n\leq 300q500q\leq 500

对于 60%60\% 的数据,n10000n\leq 10000q500q\leq 500

对于 100%100\% 的数据,1n3×1051\leq n\leq 3\times 10^51q3×1051\leq q\leq 3\times 10^51Ai1061\leq A_i\leq 10^61LiRin1\leq L_i\leq R_i\leq n

代码源挑战赛 Round 15

Not Attended
Status
Done
Rule
DMY
Problem
6
Start at
2025-6-6 20:00
End at
2025-6-6 21:30
Duration
1.5 hour(s)
Host
Partic.
579