明显的数据结构题
这道题的特殊性在于n只有10000，修改的操作只有1000
那么就是说即便是O(n)的修改也没有太大的问题，只要常数写小一点即可
考虑到以前对同色点的处理
pre[i]表示与这个位置同色的前一个位置
对于一段区间l,r，如果区间中位置i，满足pre[i]<l则这个位置上的颜色是一种，被算一次
直接扫描显然O(n),但假如这段位置pre有序，我们就可以用二分
但是如果整体排序我们就不好确定区间的位置
因此我们考虑分块，每块内pre排序，当查询区间[l,r]时
先暴力统计l，r所在块内，在用二分统计在l，r所在块之间的块每块中符合条件的个数
这样的复杂度还是可以接受了
然后考虑修改，首先修改只会对原来颜色和修改成颜色的位置产生影响
我们只要找到原来颜色的下一个同色点位置并修改所在块，
并且找到现在颜色的下一个同色点位置并修改所在块
当然这个位置的所在块也是要修改的
var p,pre,b,a:array[..] of longint;
v:array[..] of boolean;
last:array[..] of longint;
t,n,m,size,i,x,y:longint;
ch:char; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=b[(l+r) div ];
repeat
while b[i]<x do inc(i);
while x<b[j] do dec(j);
if not(i>j) then
begin
y:=b[i];
b[i]:=b[j];
b[j]:=y;
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function find(x,y:longint):longint;
var l,r,m,f:longint;
begin
l:=(x-)*size+;
f:=l;
r:=x*size;
if r>n then r:=n;
while l<=r do
begin
m:=(l+r) shr ;
if b[m]<y then l:=m+
else r:=m-;
end;
exit(l-f);
end; function ask(l,r:longint):longint;
var i:longint;
begin
ask:=;
if p[l]=p[r] then
begin
for i:=l to r do //l,r在一个块
if pre[i]<l then inc(ask);
end
else begin //不在一个块
for i:=l to p[l]*size do
if pre[i]<l then inc(ask);
for i:=(p[r]-)*size+ to r do
if pre[i]<l then inc(ask);
for i:=p[l]+ to p[r]- do
ask:=ask+find(i,l);
end;
end; procedure build(x:longint);
var l,r,i:longint;
begin
l:=(x-)*size+;
r:=x*size;
if r>n then r:=n;
for i:=l to r do
b[i]:=pre[i]; //另开一个数组排序方便二分
sort(l,r);
end; procedure change(x,y:longint);
var i,j,k:longint;
begin
if a[x]=y then exit;
fillchar(v,sizeof(v),false);
i:=last[a[x]];
k:=pre[x];
v[p[x]]:=true;
j:=;
while i<>x do
begin
j:=i;
i:=pre[i];
end;
if j<> then
begin
pre[j]:=k;
v[p[j]]:=true; //原来颜色的下一个同色点的位置所在块要修改
end
else last[a[x]]:=pre[i]; //如果是原来颜色的最后一个位置 a[x]:=y;
i:=last[y];
if x>i then //如果是现在颜色的最后一个位置
begin
last[y]:=x;
pre[x]:=i
end
else begin
while not((pre[i]<x) and (x<i)) do i:=pre[i];
pre[x]:=pre[i]; //在现在颜色的链上上插入这个位置
v[p[i]]:=true; //现在颜色的下一个同色点所在位置要修改
pre[i]:=x;
end;
for i:= to t do
if v[i] then build(i);
end; begin
readln(n,m);
for i:= to n do
read(a[i]);
readln;
size:=trunc(sqrt(n)+ln(*n)/ln()); //因为查询的复杂度带了一个logn，所以块的大小这样合适
fillchar(last,sizeof(last),);
t:=;
for i:= to n do
begin
p[i]:=t; //每个位置所在块的编号
pre[i]:=last[a[i]];
last[a[i]]:=i;
if i mod size= then inc(t);
end;
if n mod size= then dec(t);
for i:= to t do
build(i); for i:= to m do
begin
readln(ch,x,y);
if ch='Q' then writeln(ask(x,y))
else change(x,y);
end;
end.