P7875 "SWTR-7" IOI 2077

#### Friendly reminder: the input and output size of this problem is very large, please do not use `cin` or `scanf`. Fast input and its usage are provided at the bottom of the statement. #### Contest reminder: if there is no solution for the chosen $m$, then the expected value is $0$. You can combine this with the explanation of Sample 2 to understand better. #### Contest reminder: you need to compute the expected value of the sum of abilities, not the maximum. --- Little A was appointed by FCC to participate in IOI 2077! A 71-year-old veteran asks to join the battle!

There are $n$ **candidate** contestants in IOI 2077, numbered $1 \sim n$. Each candidate contestant has an ability value, and **all ability values are distinct**. The ability value of the $i$-th candidate is $a_i$. Little A prefers ordered numbers, so he sorts these $n$ candidates by ability value in **increasing** order, i.e. **$a_i < a_{i+1}\ (1 \leq i < n)$.** The official contestants will be chosen from these $n$ candidates. Specifically, all contestants will be a substring $[l, r]$ of the candidates, i.e. candidates with indices $l, l+1, \cdots, r$ will participate in IOI 2077. Little A’s index is $k$. Since he knows he has been appointed to participate, we must have $l \leq k \leq r$. There are $q$ possible cases of contestants. Each case is described by three numbers $l_i, r_i, k_i\ (l_i \leq k_i \leq r_i)$, meaning the contestants are the candidates with indices in $[l_i, r_i]$, and Little A’s index is $k_i$. Because he is not strong enough, Little A feels overwhelmed by the coming IOI. He decides to choose some contestants as teammates and help (zuo) each other (bi) during the contest. Specifically, let the number of official contestants be $s$. Then Little A will choose an integer $m$ **uniformly at random** from $[0, \lfloor \frac{s-1}{2} \rfloor]$, and then **randomly** select $2m$ people from the $s$ contestants as his teammates. However, Little A does not want to look too weak, so **his ability value $a_k$ must be the median of the ability values of these $2m+1$ people**. As the saying goes, there is strength in numbers. Little A hopes the sum of the ability values of himself and all selected teammates is as large as possible. **But before that, he wants to know the expected value of this sum**. Output the result modulo $998244353$, and it is guaranteed that the answer is well-defined under this modulus. **For each possible contestants case, you need to compute the answer for that case. To avoid too much output, you only need to compute the XOR of all answers.**

The first line contains an integer $t$, **the Subtask id of this test point.** The second line contains two integers $n, q$, representing the number of candidate contestants and the total number of cases. The third line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the ability values of each candidate contestant. **It is guaranteed that $a_i$ is increasing.** The next $q$ lines each contain three integers $l_i, r_i, k_i$ describing one possible contestants case.

Output one line with one integer, the XOR of all answers.

**"Sample 1 Explanation"** - Query 1: Since $s_1 = r_1 - l_1 + 1 = 5$, $m$ can be $0, 1$, or $2$. When $m = 0$: Little A has no teammates, so the expected value is his own ability value $a_{k_1} = a_3 = 5$. When $m = 1$: Little A can choose contestants with **indices** $(1, 4)$ or $(1, 5)$ or $(2, 4)$ or $(2, 5)$ as his teammates. The sums of abilities are $14, 15, 15, 16$ respectively, so the expected value is $\frac{14+15+15+16}{4} = 15$. When $m = 2$: Little A can only choose everyone, so the expected value is $2+3+5+7+8 = 25$. Therefore, the expected value is $\frac{5+15+25}{3} = 15$. - Query 2: Since $s_2 = r_2 - l_2 + 1 = 3$, $m$ can be $0$ or $1$. When $m = 0$: Little A has no teammates, and the expected value is $3$. When $m = 1$: Little A cannot make any choice, so the expected value is $0$. Therefore, the expected value is $\frac{3+0}{2} = \frac{3}{2}$, which becomes $499122178$ after taking modulo $998244353$. $15 \oplus 499122178 = 499122189$. **"Constraints and Conventions"** **This problem uses bundled tests.** Let $s_i = r_i - l_i + 1$. - Subtask #0 (1 point): the samples. - 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): no special constraints. For $100\%$ of the testdata, $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 < a_{i+1}\ (1 \leq i < n)$. For all test points, the time limit is 1s and the memory limit is 512MB. **"Help / Tips"** About [modulo of rational numbers](https://www.luogu.com.cn/problem/P2613), [median](https://baike.baidu.com/item/%E4%B8%AD%E4%BD%8D%E6%95%B0/3087401?fr=aladdin). The input and output size of this problem is **extremely** large, **please pay attention to I/O optimization.** This problem provides a fast input template for **signed 32-bit integers**, guaranteeing the total reading time does not exceed 250ms: ```cpp #define gc getchar() inline int read(){ int x=0; bool sgn=0; char s=gc; while(!isdigit(s))sgn|=s=='-',s=gc; while(isdigit(s))x=(x*"I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens."* >>*"I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you ............"* 2077.7.7 Translated by ChatGPT 5