众数
Time Limit : 20000/10000ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有一个长度为 $ n $ 的整数序列 $ a_1,a_2,\cdots,a_n $，序列中每个元素 $ a_i $ 都在 $ 1\sim n $ 中**等概率随机**生成。
定义一个序列 $ b_1,b_2,\cdots,b_m $ 的价值 $ \operatorname{val}(b_1,b_2,\cdots,b_m) $ 为其所有连续子序列的最大值的众数（即出现次数最大的数），当有多个众数时选择值最大的众数。
给出 $ q $ 次询问，每次询问给定两个整数 $ l,r $，问 $ \operatorname{val}(a_{l},a_{l+1},\cdots,a_r) $。
定义一个序列 $ b_1,b_2,\cdots,b_m $ 的价值 $ \operatorname{val}(b_1,b_2,\cdots,b_m) $ 为其所有连续子序列的最大值的众数（即出现次数最大的数），当有多个众数时选择值最大的众数。
给出 $ q $ 次询问，每次询问给定两个整数 $ l,r $，问 $ \operatorname{val}(a_{l},a_{l+1},\cdots,a_r) $。
Input
本题单个测试点内包含多组测试数据。
第一行一个整数 $ T(1\leq T\leq 3) $，表示数据组数。
对于每组数据，第一行两个整数 $ n,q $ $ (1\leq n,q\leq 2\times 10^5) $，分别表示序列长度和询问次数。
第二行 $ n $ 个整数 $ a_1,a_2,\cdots,a_n $ $ (1\leq a_i\leq n) $，表示序列。
接下来 $ q $ 行，每行两个整数 $ l_i,r_i $ $ (1\leq l_i\leq r_i\leq n) $，表示一次询问。
第一行一个整数 $ T(1\leq T\leq 3) $，表示数据组数。
对于每组数据，第一行两个整数 $ n,q $ $ (1\leq n,q\leq 2\times 10^5) $，分别表示序列长度和询问次数。
第二行 $ n $ 个整数 $ a_1,a_2,\cdots,a_n $ $ (1\leq a_i\leq n) $，表示序列。
接下来 $ q $ 行，每行两个整数 $ l_i,r_i $ $ (1\leq l_i\leq r_i\leq n) $，表示一次询问。
Output
对于每组数据，由于输出很大，假设原来第 $i$ 个询问的答案是 $x_i$，你只需要输出一行一个整数：
$$
\bigoplus_{i=1}^{q}i\cdot x_i
$$
即 $i$ 和 $x_i$ 乘积的异或和即可。
$$
\bigoplus_{i=1}^{q}i\cdot x_i
$$
即 $i$ 和 $x_i$ 乘积的异或和即可。
Sample Input
1 5 3 1 2 2 1 3 1 5 2 3 3 5
Sample Output
15
Hint
三次询问的答案分别为 $2,2,3$。
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）