← 返回题目列表

AtCoder · abc242_g

G. 范围配对查询

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

分数: 600 点

问题陈述

N 人数 1,2,\dots,N 站成一排。人 i 穿着颜色 A_i.

答案 Q 以下格式的查询。

  • 给你整数 l 和 r。只考虑人 l,l+1,\dots,r,最多可以组成多少对穿着相同颜色的人? 每个查询中的

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 10^5
  • 1 \le Q \le 10^6
  • 1 \le A_i \le N
  • 1 \le l \le r \le N 。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

在这里, \mathrm{Query}_i 代表 i- 第一个查询。

每个查询均采用以下格式:

l r

输出

打印 Q 行。 的 i- 第行应包含以下问题的答案 i-第一个查询作为整数。 由于可能存在较大的输入和输出,建议使用快速输入和输出方法。


样本输入 1

10
1 2 3 2 3 1 3 1 2 3
6
6 10
5 8
3 6
4 4
1 6
1 10

示例输出 1

2
2
1
0
3
4

我们有 A=(1,2,3,2,3,1,3,1,2,3)。此输入包含六个查询。

第一个查询是 (l, r) = (6, 10)。通过配对人 6, 8 和配对人 7, 10,我们可以组成两对穿着相同颜色的人。

第二个查询是 (l, r) = (5, 8)。通过配对人 5, 7 和配对人 6, 8,我们可以组成两对穿着相同颜色的人。

可以查询哪里 l=r.