记录编号	421819	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	0.425 s
提交时间	2017-07-08 10:26:46	内存使用	0.58 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
vector<int> pos[10100];
map<int,int> ma;
inline int read()
{
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
    if(ch=='-')
      f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
    x=(x<<3)+(x<<1)+ch-'0';
    ch=getchar();
  }
  return x*f;
}
int n,m,len,x,y,ji=0;
int a[10010],match[10010],pre[10010],cop[10010];
char s;
int query(int x,int y)
{
  int shu=0;
  if(match[x]+1>=match[y])
  {
    for(int i=x;i<=y;++i)
      if(cop[i]<x)
        shu++;
  }
  else
  {
    for(int i=x;i;++i)
    {
      if(match[x]!=match[i])
        break;
      if(cop[i]<x)
      {
        shu++;
      }
    }
    for(int i=y;i;--i)
    {
      if(match[y]!=match[i])
        break;
      if(cop[i]<x)
      {
        shu++;
      }
    }
    for(int i=match[x]+1;i<=match[y]-1;++i)
    {
      int l=(i-1)*len+1,r=(i-1)*len+len,mid;
      while(l<=r)
      {
        mid=(l+r)/2;
        if(pre[mid]<x)
          l=mid+1;
        else
          r=mid-1;
      }
      shu+=l-(i-1)*len-1;
    }
  }
  return shu;
}
void change(int x,int y)
{
  a[x]=y;
  if(ma.count(a[x]))
  {
    a[x]=ma[a[x]];
  }
  else
  {
    ji++;
    a[x]=ma[a[x]]=ji;
  }
  for(int i=x+1;i<=n;++i)
  {
    if(cop[i]==x)
    {
      cop[i]=cop[x];
      for(int j=(match[i]-1)*len+1;j<=min(match[i]*len,n);++j)
        pre[j]=cop[j];
      sort(pre+(match[i]-1)*len+1,pre+min(match[i]*len,n)+1);
      break;
    }
  }
  for(int i=x+1;i<=n;++i)
  {
    if(a[i]==a[x])
    {
      cop[i]=x;
      for(int j=(match[i]-1)*len+1;j<=min(match[i]*len,n);++j)
        pre[j]=cop[j];
      sort(pre+(match[i]-1)*len+1,pre+min(match[i]*len,n)+1);
      break;
    }
  }
  pre[x]=0;
  cop[x]=0;
  for(int i=x-1;i>=1;--i)
  {
    if(a[i]==a[x])
    {
      cop[x]=i;
      break;
    }
  }
  for(int j=(match[x]-1)*len+1;j<=min(match[x]*len,n);++j)
    pre[j]=cop[j];
  sort(pre+(match[x]-1)*len+1,pre+min(match[x]*len,n)+1);
}
int main()
{
  freopen("nt2011_color.in","r",stdin);
  freopen("nt2011_color.out","w",stdout);
  //memset(pre,0x3f,sizeof(pre));
  //memset(cop,0x3f,sizeof(cop));
  n=read();m=read();
  len=(int)sqrt(n+0.5);
  //len=50;
  for(int i=1;i<=n;++i)
  {
    a[i]=read();
    if(ma.count(a[i]))
    {
      a[i]=ma[a[i]];
    }
    else
    {
      ji++;
      a[i]=ma[a[i]]=ji;
    }
    if(pos[a[i]].empty())
      pre[i]=cop[i]=0;
    else
      pre[i]=cop[i]=pos[a[i]][pos[a[i]].size()-1];
    pos[a[i]].push_back(i);
  }
  //for(int i=1;i<=n;++i)
    //for(int j=i-1;j>=1;--j)
      //if(a[j]==a[i])
        //pre[i]=cop[i]=j;
  for(int i=1;i<=n;++i)
    match[i]=(i-1)/len+1;
  for(int i=1;i<=match[n];++i)
    sort(pre+(i-1)*len+1,pre+min(i*len,n)+1);
  for(int i=1;i<=m;++i)
  {
    scanf("%s",&s);
    x=read();y=read();
    if(s=='Q')
    {
      int e=query(x,y);
      printf("%d\n",e);
    }
    if(s=='R')
    {
      change(x,y);
    }
  }
  //system("pause");
  return 0;
}