额外提供 $60\%$ 的时间。
小 S 举办了一场 OI 比赛，这场比赛有 $n$ 位参赛者，编号分别为 $1,2,3,…,n$。比赛结束后，编号为 $i$ 的参赛者的分数为 $a[i]$。
小 S 认为，分数高于一定标准分数 $r$ 的参赛者，可以直接晋级；而分数低于一定标准分数 $l$ 的参赛者，会被直接淘汰。基于某些原因，小 S 认为其他参赛者的代码需要进行重测。小 S 想知道有哪些参赛者的代码需要重测。
由于小 S 会随时改变主意，因为他会询问你 $q$ 次，对于第 $i$ 次询问：
- 他会给你两个标准分数 $l[i],r[i]$，分数高于 $r[i]$ 的参赛者会直接晋级，而分数低于 $l[i]$ 的参赛者会直接淘汰。
- 小 S 关心的是需重测的参赛者的编号之和是什么。你需要回答这个答案。
從标准输入 (stdin) 读入数据。
输入的第一行包含两个正整数 $n,q$，以空格分隔。
第二行包含 $n$ 个正整数 $a[1],a[2],a[3],…,a[n]$，以空格分隔。
接下来 $q$ 行，第 $i$ 行表示第 $i$ 次询问：
- 包含两个正整数 $l[i],r[i]$，以空格分隔。
输出到标准输出 (stdout) 中。
为了减少输出量，记第 $i$ 次询问的答案为 $ans[i]$，你只需要输出
$(1×ans[1])⊕(2×ans[2])⊕(3×ans[3])⊕…⊕(q×ans[q]) \mod 2^{64}$ 的值。其中 $⊕$ 表示二进制按位异或运算。
8 2 72 93 2 82 23 10 45 33 23 45 17 92
38
对于第一次询问：编号为 $5,7,8$ 的参赛者需重测，编号之和为 $5+7+8=20$。
对于第二次询问：编号为 $1,4,5,7,8$ 的参赛者需重测，编号之和为 $1+4+5+7+8=25$。
应输出 $(1×20)⊕(2×25) \mod 2^{64}=38$。
数据范围：
- $n≤10^6$
- $q≤10^6$
- 对于所有满足 $1≤i≤n$ 的整数 $i$，$a[i]≤10^9$。
- 对于所有满足 $1≤i≤q$ 的整数 $i$，$l[i]\le r[i]\le 10^9$。
测试点 $1,2$ 满足：$n\le 1000, q\le 1000, a[i]\le 1000$。
测试点 $3,4$ 满足：$a[i]\le 10^6, l[i]=1$。
测试点 $5,6$ 满足：$a[i]\le 10^6$。
测试点 $7,8$ 满足：$a[i]\le a[i+1]$。
测试点 $9,10$ 没有额外的约束条件。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||