Breed Counting

题目描述

农夫约翰的 $N$ 头奶牛（方便起见编号为 $1 \ldots N$）都站成一排（它们似乎经常这样做，以至于现在几乎不需要农夫约翰怎么催促就会排好队）。每头奶牛都有一个品种编号：1 表示荷斯坦牛（Holsteins），2 表示根西牛（Guernseys），3 表示泽西牛（Jerseys）。农夫约翰希望你帮助他统计在队列顺序的某些区间内，每个品种的奶牛分别有多少头。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq N \leq 100,000$，$1 \leq Q \leq 100,000$）。 接下来的 $N$ 行每行包含一个整数，取值为 1、2 或 3，表示队列中对应位置上一头奶牛的品种编号。 接下来的 $Q$ 行每行描述一个查询，形式为两个整数 $a, b$（$a \leq b$）。

输出格式

对于每个查询 $(a,b)$，输出一行包含三个数：编号在 $a \ldots b$ 范围内的荷斯坦牛（品种 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

提示

题目致谢：Nick Wu

标签: USACO|2015|Silver

来源

USACO|2015|Silver