P11750 「TPOI-1D」Thank You

> もしも もう一度 あなたに会えるなら > If I could meet you once more > たった一言伝えたい ありがとう ありがとう > I just want to say one thing: thank you, thank you > —— KOKIA「[ありがとう…](https://www.bilibili.com/video/BV12W421X7MQ/)」

Misaka Mikoto gives you a sequence $[a_1, \dots, a_n]$ of length $n$ and $m$ intervals $[l_1, r_1], \dots, [l_m, r_m]$. There are $q$ queries in the form $L, R, k$. For each query, compute: $$\max_{i=L}^R \sum_{j=l_i}^{r_i} [a_j = k]$$

N/A

N/A

**This problem uses bundled tests.** - Subtask 1 (5 points): $n, m, q \le 500$. - Subtask 2 (5 points): $n, m, q \le 5000$. - Subtask 3 (5 points): At most 100 distinct elements in sequence $a$. - Subtask 4 (5 points): Each element in $a$ appears at most 10 times. - Subtask 5 (20 points): $n, m, q \le 5 \times 10^4$. - Subtask 6 (20 points): $n, m, q \le 10^5$. - Subtask 7 (40 points): No additional constraints. For $100\%$ data: $1 \le n, m, q \le 2 \times 10^5$, $1 \le a_i, k \le n$, $1 \le l_i \le r_i \le n$, $1 \le L \le R \le m$. Translated by DeepSeek R1