Range Pairing Query

题目描述

$N$ 个人按编号 $1,2,\dots,N$ 站成一排。第 $i$ 个人穿着颜色 $A_i$。 回答 $Q$ 个如下格式的查询。

给定整数 $l$ 和 $r$。只考虑第 $l,l+1,\dots,r$ 个人，最多可以形成多少对穿相同颜色的人员配对？

输入格式

输入按照下述格式从标准输入给出： $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$ 个查询的答案，作为一个整数。 建议使用快速的输入输出方法以应对可能大量的输入输出。

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

2
2
1
0
3
4

提示

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

标签: AtCoder|abc242G

来源

AtCoder|abc242G