TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8131
  • 题目
  • P8131统计血统
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    农夫约翰有n 头奶⽜,为了⽅便我们把它们编号为1 ~ n,现在它们站成了⼀排。每头奶 ⽜都有⼀个⾎统的类型:1 代表荷斯坦奶⽜,2 代表根⻄奶⽜,3 代表泽⻄奶⽜。农夫约翰想要 你帮忙数⼀下某些特定的区间内,每种奶⽜各有多少头。

    输入格式

    第⼀⾏包含两个整数n 和q,表示奶⽜的头数和询问数。 第⼆⾏包含n 个正整数,每个是1; 2 或3 中的⼀个,表示每头奶⽜的⾎统。 接下来q ⾏,每⾏两个整数a; b,询问区间a, a + 1, ...... , b 的情况。

    输出格式

    输出⽂件共q ⾏,每⾏三个⽤空格隔开的⾮负整数,分别代表每种奶⽜的数量。

    样例输入

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

    样例输出

    3 2 1
    1 0 0
    2 0 1

    提示

    对于编号为 $1 \sim 3$ 的测试点,满足 \(n, q \leqslant 1000\)。 对于编号为 $4 \sim 14$ 的测试点,满足 \(n, q \leqslant 100000\)。 对于所有的测试点,保证 $1 \leqslant a \leqslant b \leqslant n$ 。