AT_abc293_g.[ABC293G] Triple Index

给定一个长度为 $N$ 的正整数序列 $(A_1,\ A_2,\ \ldots,\ A_N)$，以及关于该序列的 $Q$ 个查询。

对于每个 $q = 1, 2, \ldots, Q$，第 $q$ 个查询给出一对整数 $(l_q,\ r_q)$，请输出满足以下两个条件的整数三元组 $(i,\ j,\ k)$ 的个数：

• $l_q \leq i < j < k \leq r_q$
• $A_i = A_j = A_k$

输入以如下格式从标准输入中给出。

$N$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

输出 $Q$ 行。对于 $q = 1, 2, \ldots, Q$，第 $q$ 行输出第 $q$ 个查询的答案。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• $1 \leq l_q \leq r_q \leq N$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个查询，满足题目中两个条件的三元组 $(i,\ j,\ k)$ 有 $(1, 5, 9),\ (4, 6, 8),\ (4, 6, 10),\ (4, 8, 10),\ (6, 8, 10)$ 共 $5$ 个。

由 ChatGPT 4.1 翻译