USACO 2015 December Contest · Silver

题目 3：奶牛品种统计（Breed Counting）

题目描述

农夫 John 的 N 头奶牛整齐地排成一排，编号为 1…N。

每头奶牛都有一个 ​品种编号​：

• 1 表示 Holsteins（荷斯坦牛）
• 2 表示 Guernseys（根西牛）
• 3 表示 Jerseys（泽西牛）

农夫 John 想统计：在某些区间内，每种品种的奶牛分别有多少头。

给定多次查询，每次查询一个区间 [a, b]，你需要输出：

• 区间内 品种 1 的奶牛数量
• 区间内 品种 2 的奶牛数量
• 区间内 品种 3 的奶牛数量

---

输入格式

第一行包含两个整数：

N Q

• N 表示奶牛数量
• Q 表示查询数量

接下来 N 行，每行一个整数：

breed_i

表示第 i 头奶牛的品种编号（1、2 或 3）。

接下来 Q 行，每行两个整数：

a b

表示一次查询区间 [a, b]。

---

输出格式

对于每一次查询 [a, b]，输出一行三个整数：

count1 count2 count3

分别表示区间 [a, b] 内：

• 品种 1 的奶牛数量
• 品种 2 的奶牛数量
• 品种 3 的奶牛数量

数字之间用空格分隔。

---

数据范围

1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ a ≤ b ≤ N
breed_i ∈ {1,2,3}

---

样例输入

6 3
2
1
1
3
2
1
1 6
3 3
2 4

---

样例输出

3 2 1
1 0 0
2 0 1

---

样例解释

奶牛品种序列为：

2 1 1 3 2 1

查询结果：

1️⃣ 查询 [1,6]

1号品种：3
2号品种：2
3号品种：1

2️⃣ 查询 [3,3]

只有第3头牛 → 品种1

3️⃣ 查询 [2,4]

1 1 3

统计得到：

2 0 1

---