← 返回题目列表

AtCoder · abc293_g

G. 三重索引

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个长度-N 序列 (A_1, A_2, \ldots, A_N) 正整数,以及 Q 有关序列的查询。

对于每个 q = 1, 2, \ldots, Q, q-th 查询为您提供一个整数对 (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