题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2120
题意：给出一个数列，两种操作：（1）询问区间[L,R]内有多少不同的数字；（2）修改某个位置的数字。
思路：首先分块。然后用sum[L][R][x]记录从第L块到第R块数字x出现的次数，cnt[L][R] 表示从第L块到第R块不同数字的个数。分块后可以预处理出初始时的sum和cnt数组。对于查询，[L,R]，可能不是完整占据某段连续的块，需要将零头加上，之后输出答案再将零头减去；对于修改，找到包含修改位置所在块的所有区间修改sum和cnt数组。
int pl[25],pr[25],pNum,cnt[25][25],sum[25][25][N];
int f[N*100],K,size;
int n,m;
int a[N];
int F(int k)
{
if(!f[k]) f[k]=++K;
return f[k];
}
void deal()
{
int x,y,i,j,k,ll,rr;
char op[5];
while(m--)
{
RD(op); RD(x,y);
if(op[0]=='Q')
{
ll=0; rr=pNum;
while(pl[ll]<x) ll++;
while(pr[rr]>y) rr--;
for(i=x;i<=min(y,pr[ll-1]);i++)
{
if(++sum[ll][rr][a[i]]==1) cnt[ll][rr]++;
}
for(i=max(x,pl[rr+1]);i<=y;i++)
{
if(++sum[ll][rr][a[i]]==1) cnt[ll][rr]++;
}
PR(cnt[ll][rr]);
for(i=x;i<=min(y,pr[ll-1]);i++)
{
if(0==--sum[ll][rr][a[i]]) cnt[ll][rr]--;
}
for(i=max(x,pl[rr+1]);i<=y;i++)
{
if(0==--sum[ll][rr][a[i]]) cnt[ll][rr]--;
}
}
else
{
k=0;
while(pr[k]<x) k++;
for(i=1;i<=k;i++) for(j=k;j<=pNum;j++)
{
if(0==--sum[i][j][a[x]]) cnt[i][j]--;
}
a[x]=F(y);
for(i=1;i<=k;i++) for(j=k;j<=pNum;j++)
{
if(1==++sum[i][j][a[x]]) cnt[i][j]++;
}
}
}
}
int main()
{
RD(n,m);
int i,j,k;
FOR1(i,n) RD(j),a[i]=F(j);
while(size*size*size<n) size++;
size=size*size;
int L=1,R=min(n,size);
while(L<=n)
{
pl[++pNum]=L;
pr[pNum]=R;
L=R+1;
R=min(n,R+size);
}
FOR1(i,pNum) for(j=i;j<=pNum;j++)
{
for(k=pl[i];k<=pr[j];k++)
{
if(++sum[i][j][a[k]]==1) cnt[i][j]++;
}
}
pl[0]=-INF; pr[0]=0; pl[++pNum]=n+1; pr[pNum]=INF;
deal();
}