AT_abc242_g [ABC242G] Range Pairing Query

题目描述

有 $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$ 个查询的答案，答案为一个整数。
由于输入输出数据量较大，建议使用高效的输入输出方法。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• 所有输入均为整数。
• $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$

样例解释 1

$A=(1,2,3,2,3,1,3,1,2,3)$。该输入包含 $6$ 个查询。第 $1$ 个查询为 $(l,r)=(6,10)$。可以将第 $6$ 号人与第 $8$ 号人配对，第 $7$ 号人与第 $10$ 号人配对，这样可以组成 $2$ 对穿着相同颜色衣服的两人组。第 $2$ 个查询为 $(l,r)=(5,8)$。可以将第 $5$ 号人与第 $7$ 号人配对，第 $6$ 号人与第 $8$ 号人配对，这样也可以组成 $2$ 对穿着相同颜色衣服的两人组。也可能会有 $l=r$ 的查询。

由 ChatGPT 4.1 翻译