B. 数颜色
题目描述
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。
输出格式
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。
样例
样例输入
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6样例输出
4
4
3
4数据范围与提示
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过106。。 2016.3.2新加数据两组by Nano_Ape
这个玩意拖了一周了…今天把它补上（主要是因为AC自动机卡住了）。
网上用莫队和分块的比较多，然而我都不会……所以就用数据结构写了，其实就是待修改的主席树。
先预处理出 prei 表示位置 i 前第一个和位置 i 颜色相同的位置（map实现），则区间 [L, R] 里有多少不同的数就转化为了求区间 [L, R] 里prei < L 的位置个数，对 pre 数组建主席树（权值线段树），差不多和板子 一样，只是询问要稍微改一下：
inline int ask(int u,int v,int a,int b,int l,int r,int k)
{
if(l==r)return ;
int lm=sum(l(b))+Sum(,v)-sum(l(a))-Sum(,u),
mid=(l+r)>>;
if(k<=mid)
{
for(int i=u;i>=;i-=lowbit(i))
use[][i]=l(use[][i]);
for(int i=v;i>=;i-=lowbit(i))
use[][i]=l(use[][i]);
return ask(u,v,l(a),l(b),l,mid,k);
}
else
{
for(int i=u;i>=;i-=lowbit(i))
use[][i]=r(use[][i]);
for(int i=v;i>=;i-=lowbit(i))
use[][i]=r(use[][i]);
return lm+ask(u,v,r(a),r(b),mid+,r,k);
}
}
对于修改，首先想到的是直接重新计算pre数组更新，但是复杂度太大肯定会超时，但是真的每个位置的pre值都会改变吗？其实若将i位置修改，最多改变三个pre：
1.i本身。
2.i之后pre=i的位置，最多一个。
3.i之后pre<i，但是值与更改后数值相等的，最多一个。
这样复杂度就可以接受了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
struct node
{
int l,r,sum;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum(x) tr[x].sum
}tr[];
int cnt,m,T[],S[],use[][];
int n,Q,a[],pre[];
map<int,int> mp; inline int read()
{
int s=;char a=getchar();
while(a<''||a>'')a=getchar();
while(a>=''&&a<=''){s=s*+a-'';a=getchar();}
return s;
}
inline int lowbit(int x){return x&(-x);}
inline int build(int l,int r)
{
int now=++cnt;
if(l==r)return now;
int mid=(l+r)>>;
l(now)=build(l,mid);
r(now)=build(mid+,r);
return now;
}
inline int build_new(int flag,int mark,int loc,int val)
{
int rt=++cnt;
int before;
if(mark==)before=T[];
else before=flag?T[mark-]:S[mark-];
if(!flag && val)before=S[mark];
sum(rt)=sum(before)+val;
int l=,r=n+,mid,now=rt,still=before;
for(;l(still)||r(still);)
{
mid=(l+r)>>;
if(loc>mid)
{
l(now)=l(still),r(now)=++cnt;
sum(cnt)=sum(r(still))+val;
now=cnt;still=r(still);
l=mid+;
}
else
{
r(now)=r(still),l(now)=++cnt;
sum(cnt)=sum(l(still))+val;
now=cnt;still=l(still);
r=mid;
}
}
return rt;
}
inline int Sum(int y,int x)
{
int res=;
for(int i=x;i>=;i-=lowbit(i))
res+=sum(l(use[y][i]));
return res;
}
inline void updata(int loc,int num)
{
for(int i=loc;i<=n+;i+=lowbit(i))
S[i]=build_new(,i,pre[loc],-);
for(int i=loc;i<=n+;i+=lowbit(i))
S[i]=build_new(,i,num,);
pre[loc]=num;
}
inline int ask(int u,int v,int a,int b,int l,int r,int k)
{
if(l==r)return ;
int lm=sum(l(b))+Sum(,v)-sum(l(a))-Sum(,u),
mid=(l+r)>>;
if(k<=mid)
{
for(int i=u;i>=;i-=lowbit(i))
use[][i]=l(use[][i]);
for(int i=v;i>=;i-=lowbit(i))
use[][i]=l(use[][i]);
return ask(u,v,l(a),l(b),l,mid,k);
}
else
{
for(int i=u;i>=;i-=lowbit(i))
use[][i]=r(use[][i]);
for(int i=v;i>=;i-=lowbit(i))
use[][i]=r(use[][i]);
return lm+ask(u,v,r(a),r(b),mid+,r,k);
}
}
signed main()
{
// freopen("in.txt","r",stdin); n=read(),Q=read();
for(int i=;i<=n;i++)
a[i]=read(),pre[i]=mp[a[i]]+,mp[a[i]]=i;
T[]=build(,n+);
for(int i=;i<=n;i++)
T[i]=build_new(,i,pre[i],);
for(int i=;i<=n;i++)
S[i]=build_new(,i,,);
char ta;int L,R;
for(int i=;i<=Q;i++)
{
cin>>ta;
L=read(),R=read();
if(ta=='Q')
{
for(int j=L-;j>=;j-=lowbit(j))
use[][j]=S[j];
for(int j=R;j>=;j-=lowbit(j))
use[][j]=S[j];
printf("%ld\n",ask(L-,R,T[L-],T[R],,n+,L+));
}
else
{
int tem=pre[L];
updata(L,);
a[L]=R;
for(int j=;j<=n;j++)
{
if(a[j]==R && j<L)
updata(L,j+);
if(pre[j]==L+)
updata(j,tem);
if(a[j]==R && j>L && pre[j]-<L)
updata(j,L+);
}
}
}
}