【bzoj2453】维护队列

2014年4月26日4,0375

Description

你小时候玩过弹珠吗?
小朋友A有一些弹珠,A喜欢把它们排成队列,从左到右编号为1到N。为了整个队列鲜艳美观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,A有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是A还没有学过编程,且觉得头脑风暴太浪费脑力了,所以向你来寻求帮助。

Input

输入文件第一行包含两个整数N和M。
第二行N个整数,表示初始队列中弹珠的颜色。
接下来M行,每行的形式为“Q L R”或“R x c”,“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中,一共有多少不同颜色的弹珠,“R x c”表示A把x位置上的弹珠换成了c颜色。

Output

对于每个Q操作,输出一行表示询问结果。

Sample Input


2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

对于100%的数据,有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000,小朋友A不会修改超过1000次,所有颜色均用1到10^6的整数表示。

题解

用pre[i]记录前一个和i相同颜色的球的所在位置

询问l到r时,如果pre[i]<r说明在l到i这一段没用和i颜色相同的球,则ans++

利用这种思路我们可以。。。分块

每一块内按pre[i]排序,然后和教主的魔法那题都一样了

 

  • 蒟蒻2016年2月25日 下午7:17 回复

    觉得黄学长这题的主席树差不多也就100行,跑得飞起23333

    #1  
  • sigma_poet2016年3月16日 上午11:48 回复

    黄学长,明明是小于pre[i] < l说明没有,为啥是< r

    #2  
  • 蒟蒻2016年3月22日 下午7:13 回复

    不明白,求解

    #3  
  • 蒟蒻konjac2017年3月30日 上午7:55 回复

    应该是pre[i] < l吧

    #4  
  • IAMACER2017年4月20日 上午8:30 回复

    显然是pre[i]<l

    #5