TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2182
  • Problem
  • P2182【河北OI 2012 DAY1】采花
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

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

    Sample Output

    2
    0
    0
    1
    0

    Hint

    【样例说明】
    询问[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\)