102936: [Atcoder]ABC293 G - Triple Index

Problem Statement

You are given a length-$N$ sequence $(A_1, A_2, \ldots, A_N)$ of positive integers, and $Q$ queries about the sequence.

For each $q = 1, 2, \ldots, Q$, the $q$-th query gives you an integer pair $(l_q, r_q)$;
print the number of integer triplets $(i, j, k)$ such that

• $l_q \leq i \lt j \lt k \leq r_q$, and
• $A_i = A_j = A_k$.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. For $q = 1, 2, \ldots, Q$, the $q$-th line should contain the answer to the $q$-th query.

Sample Input 1

10 4
2 7 1 8 2 8 1 8 2 8
1 10
1 9
2 10
5 5

Sample Output 1

5
2
4
0

For the first query, there are five triplets of integers that satisfy the conditions in the problem statement: $(1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10)$, and $(6, 8, 10)$.

Sample Input 2

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12

Sample Output 2

1
0
5
2
0
1
11
55
8
1

问题描述

给你一个长度为$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 \lt j \lt k \leq r_q$，和
• $A_i = A_j = A_k$。

限制条件

• $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$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

$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

10 4
2 7 1 8 2 8 1 8 2 8
1 10
1 9
2 10
5 5

样例输出1

5
2
4
0

对于第一个查询，有五个满足题目描述中条件的整数三元组： $(1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10)$和$(6, 8, 10)$。

样例输入2

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12

样例输出2

1
0
5
2
0
1
11
55
8
1