墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？
Input
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。
Output
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。
Sample Input6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
Sample Output4 4 3 4 Hint
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
思路： 假如没有修改操作，就是很常见的主席树求区间不同数的个数：把下边i看成x轴，对用的前缀pre[i]看成y轴，然后就可以用主席树求矩形内（s轴范围的[L,R]，y轴范围的[0,L-1]）的点的个数。 考虑修改操作，因为主席树只用到差分，我们想到可以用数状数组求前缀和差分。那么把普通的主席树转化为数状数组套主席树：对于每个x=i，我们加一个点，等效于y=[pre[i],N]范围都加1。即用数状数组表示为：
for(j=i;j<=N;j+=(-j)&j) add(rt[j],,tN,Laxt[a[i]],);//即对于的主席树都更改，达到记录前缀和的效果。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
struct in{ int l,r,sum; }p[maxn];
int a[maxn],b[maxn],Laxt[maxn],x[maxn],y[maxn],rt[maxn];
int N,M,tN,cnt; char c[maxn][];
set<int>s[maxn];
set<int>::iterator it,pre,lat;
void add(int &Now,int L,int R,int pos,int val)
{
if(!Now) Now=++cnt; p[Now].sum+=val;
if(L==R) return ; int Mid=(L+R)>>;
if(pos<=Mid) add(p[Now].l,L,Mid,pos,val);
else add(p[Now].r,Mid+,R,pos,val);
}
int query(int Now,int L,int R,int l,int r)
{
if(l<=L&&r>=R) return p[Now].sum;
int res=,Mid=(L+R)>>;
if(l<=Mid) res+=query(p[Now].l,L,Mid,l,r);
if(r>Mid) res+=query(p[Now].r,Mid+,R,l,r);
return res;
}
int main()
{
int i,j; scanf("%d%d",&N,&M);
for(i=;i<=N;i++) scanf("%d",&a[i]),b[++tN]=a[i];
for(i=;i<=M;i++){
scanf("%s%d%d",c[i],&x[i],&y[i]);
if(c[i][]=='R') b[++tN]=y[i];
}
sort(b+,b+tN+);
tN=unique(b+,b+tN+)-(b+);
for(i=;i<=N;i++) {
a[i]=lower_bound(b+,b+tN+,a[i])-b;
for(j=i;j<=N;j+=(-j)&j) add(rt[j],,tN,Laxt[a[i]],);
s[a[i]].insert(i); Laxt[a[i]]=i;
}
for(i=;i<=tN;i++) s[i].insert();
for(i=;i<=M;i++){
if(c[i][]=='Q'){
int ans=;
for(j=y[i];j;j-=(-j)&j) ans+=query(rt[j],,tN,,x[i]-);
for(j=x[i]-;j;j-=(-j)&j) ans-=query(rt[j],,tN,,x[i]-);
printf("%d\n",ans);
}
else {
y[i]=lower_bound(b+,b+tN+,y[i])-b;
if(a[x[i]]==y[i]) continue;
it=pre=lat=s[a[x[i]]].lower_bound(x[i]); pre--; lat++;
for(j=x[i];j<=N;j+=(-j)&j) add(rt[j],,tN,*pre,-);
if(lat!=s[a[x[i]]].end()) {
for(j=*lat;j<=N;j+=(-j)&j) add(rt[j],,tN,x[i],-);
for(j=*lat;j<=N;j+=(-j)&j) add(rt[j],,tN,*pre,);
} s[a[x[i]]].erase(it); a[x[i]]=y[i]; s[a[x[i]]].insert(x[i]); it=pre=lat=s[a[x[i]]].lower_bound(x[i]); pre--; lat++;
for(j=x[i];j<=N;j+=(-j)&j) add(rt[j],,tN,*pre,);
if(lat!=s[a[x[i]]].end()) {
for(j=*lat;j<=N;j+=(-j)&j) add(rt[j],,tN,x[i],);
for(j=*lat;j<=N;j+=(-j)&j) add(rt[j],,tN,*pre,-);
}
}
}
return ;
}
（当然还可以用带修改的莫对来做，日后再补！）