P7875 「SWTR-7」IOI 2077

#### 友情提醒：本题输入输出量很大，请不要使用 cin 或 scanf。题目最下方附有快读及其使用方法。 #### 赛时提醒：若对于选出的 $m$ 无解，则期望值为 $0$。可以结合样例 2 的解释说明以更好理解。 #### 赛时提醒：你需要求的是能力值之和的期望而不是最大值。 --- 小 A 被 FCC 钦定参加 IOI 2077！71 岁老将请求出战！

IOI 2077 有 $n$ 位**候选**参赛者，他们分别编号为 $1\sim n$。每位候选参赛者都有一个能力值，且**能力值互不相等**，第 $i$ 位候选参赛者的能力值为 $a_i$。小 A 更喜欢有序的数字，所以他将这 $n$ 位候选参赛者按照能力值**从小到大**排好了序，即**满足 $a_i

第一行一个整数 $t$，**表示该测试点 Subtask 编号。** 第二行两个整数 $n,q$，分别表示候选参赛者个数和情况总数。 第三行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个候选参赛者的能力值。**保证 $a_i$ 递增。** 接下来 $q$ 行，每行三个整数 $l_i,r_i,k_i$ 描述一个可能的参赛者情况。

输出一行一个整数，表示所有答案的异或和。

**「样例 1 说明」** - 第 1 个询问： 因为 $s_1=r_1-l_1+1=5$，所以 $m$ 可以为 $0,1$ 或 $2$。 $m=0$ 时：小 A 没有队友，那么期望值就是他自身的能力值 $a_{k_1}=a_3=5$。 $m=1$ 时：小 A 可以选**编号** $(1, 4)$ 或 $(1, 5)$ 或 $(2, 4)$ 或 $(2, 5)$ 的参赛者作为他的队友，能力值之和分别为 $14,15,15,16$，期望值为 $\frac{14+15+15+16}{4}=15$。 $m=2$ 时：小 A 只能全选，期望值为 $2+3+5+7+8=25$。 综上，期望值为 $\frac{5+15+25}{3}=15$。 - 第 2 个询问： 因为 $s_2=r_2-l_2+1=3$，所以 $m$ 可以为 $0$ 或 $1$。 $m=0$ 时，小 A 没有队友，期望值为 $3$。 $m=1$ 时，小 A 无法选择，期望值为 $0$。 综上，期望值为 $\frac{3+0}{2}=\frac{3}{2}$，对 $998244353$ 取模后为 $499122178$。 $15\oplus499122178=499122189$。 **「数据范围与约定」** **本题采用捆绑测试。** 记 $s_i=r_i-l_i+1$。 - Subtask #0（1 point）：是样例。 - Subtask #1（10 points）：$s_i\leq 2$。 - Subtask #2（20 points）：$s_i\leq 16$，$q\leq 40$，$n\leq 640$。 - Subtask #3（15 points）：$s_i,q\leq 500$，$n\leq 10^5$。 - Subtask #4（15 points）：$s_i,q\leq 3\times 10^3$，$n\leq 10^5$。 - Subtask #5（15 points）：$s_i,q\leq 2\times 10^5$，$n\leq 5\times 10^5$。 - Subtask #6（24 points）：无特殊限制。 对于 $100\%$ 的数据，$1\leq n,q\leq 2\times 10^6$，$1\leq l_i\leq k_i\leq r_i\leq n$，$1 \le a_i \le 998244352$，$a_i*“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you ............”* 2077.7.7