「BZOJ2453」维护队列

2014年4月26日7,5675

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]排序,然后和教主的魔法那题都一样了

 

avatar
5 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
IAMACER蒟蒻konjac蒟蒻sigma_poet蒟蒻 Recent comment authors
  Subscribe  
提醒
IAMACER

显然是pre[i]<l

蒟蒻konjac

应该是pre[i] < l吧

蒟蒻
蒟蒻

不明白,求解

sigma_poet
sigma_poet

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

蒟蒻

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