记录编号	367781	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.245 s
提交时间	2017-02-01 22:47:51	内存使用	4.81 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
}; using IO::readint; using IO::readc;
const int MAXN = 10002, MAXC = 1000002;
struct que{
  int l, r, tim; //triple
  int bl, br;
  int ans;
  bool operator<(const que &oq)const{
    if(bl == oq.bl){
      if(br == oq.br)return tim < oq.tim;
      else return br < oq.br;
    }else return bl < oq.bl;
  }
}qs[MAXN];
int rank[MAXN];
bool cmp(int a, int b){return qs[a] < qs[b];}
struct chg{
  int last, pos, val;
}cs[MAXN];
int col[MAXN], cnt[MAXC];
int ans;
inline void removeC(int p){if(--cnt[col[p]] == 0)ans--;}
inline void insertC(int p){if(++cnt[col[p]] == 1)ans++;}
void insertT(int t, int l, int r){
  if(cs[t].pos >= l && cs[t].pos <= r){
    removeC(cs[t].pos);
    col[cs[t].pos] = cs[t].val;
    insertC(cs[t].pos);
  }else col[cs[t].pos] = cs[t].val;
}
void removeT(int t, int l, int r){
  if(cs[t].pos >= l && cs[t].pos <= r){
    removeC(cs[t].pos);
    col[cs[t].pos] = cs[t].last;
    insertC(cs[t].pos);
  }else col[cs[t].pos] = cs[t].last;
}
int last[MAXN];
int main(){
  freopen("nt2011_color.in", "r", stdin);
  freopen("nt2011_color.out", "w", stdout);
  int n, m;
  n = readint(); m = readint();
  for(int i = 1; i <= n; i++)last[i] = col[i] = readint();
  int magic = (int)(ceil(pow(n, 2.0/3.0)));
  int cntc = 0, cntq = 0;
  for(int i = 1; i <= m; i++){
    char op;
    while(!isalpha(op = readc()));
    int a = readint(); int b = readint();
    if(op == 'Q'){
      qs[++cntq] = (que){a, b, cntc, a/magic, b/magic, cntq};
      rank[cntq] = cntq;
    }else if(op == 'R')
      cs[++cntc] = (chg){last[a], a, b}, last[a] = b;
  }
  sort(rank+1, rank+1+cntq, cmp);
  int l = 1, r = 0, t = 0;
  for(int i = 1; i <= cntq; i++){
    que &q = qs[rank[i]];
    while(t < q.tim)insertT(++t, l, r);
    while(t > q.tim)removeT(t--, l, r);
    while(l < q.l)removeC(l++);
    while(r < q.r)insertC(++r);
    while(l > q.l)insertC(--l);
    while(r > q.r)removeC(r--);
    q.ans = ans;
  }
  for(int i = 1; i <= cntq; i++)printf("%d\n", qs[i].ans);
  return 0;
}