TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2182
  • 题目
  • P2182【河北OI 2012 DAY1】采花
    限制 : 时间限制 : 50000 MS   空间限制 : 165536 KB
    问题描述

    时限:5s
    萧芸斓是Z 国的公主,平时的一大爱好是采花。
    今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花。花园足够大,容纳
    了n 朵花,花有c 种颜色(用整数1-c 表示),且花是排成一排的,以便于公主采花。
    公主每次采花后会统计采到的花的颜色数,颜色数越多她会越高兴!同时,她有一癖好,
    她不允许最后自己采到的花中,某一颜色的花只有一朵。为此,公主每采一朵花,要么此前
    已采到此颜色的花,要么有相当正确的直觉告诉她,她必能再次采到此颜色的花。
    由于时间关系,公主只能走过花园连续的一段进行采花,便让女仆福涵洁安排行程。福
    涵洁综合各种因素拟定了m 个行程,然后一一向你询问公主能采到多少朵花(她知道你是编
    程高手,定能快速给出答案!),最后会选择令公主最高兴的行程(为了拿到更多奖金!)。

    输入格式

    第一行四个空格隔开的整数n、c 以及m。
    接下来一行n 个空格隔开的整数,每个数在[1, c]间,第i 个数表示第i 朵花的颜色。
    接下来m 行每行两个空格隔开的整数l 和r(l ≤ r),表示女仆安排的行程为公主经
    过第l 到第r 朵花进行采花。

    输出格式

    共m 行,每行一个整数,第i 个数表示公主在女仆的第i 个行程中能采到的花的颜色数。

    样例输入

    5 3 5
    1 2 2 3 1
    1 5
    1 2
    2 2
    2 3
    3 5

    样例输出

    2
    0
    0
    1
    0

    提示

    【样例说明】
    询问[1, 5]:公主采颜色为1 和2 的花,由于颜色3 的花只有一朵,公主不采;
    询问[1, 2]:颜色1 和颜色2 的花均只有一朵,公主不采;
    询问[2, 2]:颜色2 的花只有一朵,公主不采;
    询问[2, 3]:由于颜色2 的花有两朵,公主采颜色2 的花;
    询问[3, 5]:颜色1、2、3 的花各一朵,公主不采。
    【数据范围】
    对于20%的数据,n ≤ 10^2,c ≤ 10^2,m ≤ 10^2;
    对于50%的数据,n ≤ 10^5,c ≤ 10^2,m ≤ 10^5;
    对于100%的数据,1 ≤ n ≤10^5,c ≤ n,m ≤ 10^5。