分数: 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.