P13688 【MX-X16-T6】「DLESS-3」XOR and Powerless Suffix Mode

我们称 $x$ 是序列 $a$ 的一个子序列中的 Powerless Suffix Mode，当且仅当： - $x$ 是该子序列的众数$^{\dagger}$。 - 不存在满足 $i < j$ 的下标 $i, j$ 使得 $a_i = a_j = x$ 且 $a_i$ 属于该子序列、$a_j$ 不属于该子序列。 - $x$ 在子序列中出现次数不超过 $x$ 在整个序列中出现次数的 $p\%$。 给定长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。给出 $q$ 次询问，每次询问给出整数 $l,r,p$（$1 \le l \le r \le n$，$1 \le p \le 100$），求序列 $b=[a_l,a_{l+1},\dots,a_{r-1},a_r]$ 所有非空子序列 Powerless Suffix Mode 的异或和（若某个子序列有多个 Powerless Suffix Mode 则全部异或，若没有则异或 $0$）。 **注意，此时判定一个数是否是 Powerless Suffix Mode 的条件中，“整个序列”为序列 $b$。** --- $^{\dagger}$一个序列的众数是指序列中出现次数最多的数，一个序列可以有多个众数，例如序列 $[1,2,1,3,2]$ 的众数有 $1$ 和 $2$。

第一行，两个整数 $n,q$。 第二行，$n$ 个整数 $a_1, \ldots, a_n$。 接下来 $q$ 行，每行三个整数 $l,r,p$，表示一次询问。

对于每次询问，输出一行一个数，表示答案。

**【样例解释 #1】** 为了方便说明，以下简称 Powerless Suffix Mode 为 PSM。 对于第一组询问，考察的序列是 $b=[1, 9, 1]$。该序列的非空子序列有 $[1]$、$[9]$、$[1]$、$[1,9]$、$[1,1]$、$[9,1]$、$[1,9,1]$。子序列 $[9]$ 的 PSM 是 $9$；子序列 $[1,9]$ 的众数是 $1$ 和 $9$，但是由于 $b_1=b_3=1$ 且 $b_1$ 在子序列中而 $b_3$ 不在，所以其中只有 $9$ 是 PSM。枚举可得，将所有子序列的 PSM 全部异或起来，最终结果为 $9$。 对于第二组询问，考察的序列是 $b=[4, 5, 1, 4]$。$p=50\%$ 的限制意味着，若一个数在子序列中成为 PSM，它的出现次数不能超过它在 $b$ 中出现次数的 $50\%$。例如，对于数 $4$，它在 $b$ 中出现 $2$ 次，那么在子序列中最多出现 $2\times 50\%=1$ 次。枚举可得，所有非空子序列的 PSM 的异或和为 $0$。 **【数据范围】** **本题采用捆绑测试。** 对于所有数据，保证 $1\le n\le 2.5\times10^5$，$1\le q\le 2.5\times10^5$，$0\le a_i