|
||||||||||
XOR-SumTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 356 Accepted Submission(s): 75 Problem Description 给出一个长度为 $n$ 的数组 $a_0,\ldots,a_{n-1}$,有 $q$ 次操作,每次询问给出 $i, X$,你要求出$\sum_{j=0}^{X} a_{i \oplus j}$,其中 $\oplus$ 表示异或操作,特别的如果 $i \oplus j \geq n$,那么 $a_{i \oplus j} = 0$。支持单点修改。 Input 第一行给出 $n, q$。 第二行给出 $n$ 个数字 $a_0, ..., a_{n-1}$。 接下来 $q$ 行,每次输入一个 $op$ 表示操作序号。 若 $op=1$, 输入 $i, v$,表示将 $a_i$ 改成 $v$。 若 $op=2$,输入 $i, X$,表示查询 $\sum_{j=0}^{X} a_{i\oplus j}$。 #### 评测数据规模 $n, q \leq 524288,op \in \{1,2\},0 \leq i, X < n, 0 \leq v, a_i \leq 10^9$。 Output 对于每个 $op=2$ 输出答案。 #### 样例解释 $a_1+a_{1\oplus1}+\ldots+a_{1\oplus 5} + a_{1\oplus 6} = 1 + 1 + 5 + 4 + 4 + 1 + 0 = 16$. 第二次操作将 $a_1$ 改为 $4$,$a = \{1,4,4,5,1,4\}$. $a_3+a_{3\oplus 1}+a_{3\oplus 2}+3_{3\oplus 3}=5+4+4+1=14$. Sample Input
Sample Output
Source | ||||||||||
|