Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

01/21
13:48
一般动规与递推

[bzoj 4397] Usaco2015dec Breed Counting

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer John's N cows, conveniently numbered 1…N, are all standing in a row (they seem to do so often that it now takes very little prompting from Farmer John to line them up). Each cow has a breed ID: 1 for Holsteins, 2 for Guernseys, and 3 for Jerseys. Farmer John would like your help counting the number of cows of each breed that lie within certain intervals of the ordering.

给定一个长度为N的序列,每个位置上的数只可能是1,2,3中的一种。

有Q次询问,每次给定两个数a,b,请分别输出区间[a,b]里数字1,2,3的个数。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

The first line of input contains NN and QQ (1≤N≤100,000 1≤Q≤100,000).
The next NN lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single cow in the ordering.
The next QQ lines describe a query in the form of two integers a,b (a≤b).

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

For each of the QQ queries (a,b), print a line containing three numbers: the number of cows numbered a…b that are Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3).

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3 2 1
1 0 0
2 0 1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

刷水真是好玩= 居然不忽略行末空格=

c++:

 

pascal:

[bzoj 4397] Usaco2015dec Breed Counting