1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
#include<algorithm> #include<cmath> using namespace std; const int N=1000050; struct { int ql,qr,t,id; } q[N]; struct update { int pos,val; } c[N]; int cnt[N],w[N],ans[N],sum=0,num,n,m; int cntq,cntc; inline int read() { register int x=0,t=1; register char ch=getchar(); while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-') {t=-1;ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();} return x*t; } inline char get() { register char ch=getchar(); while (!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z'))) ch=getchar(); return ch; } void add(int k) { if(++cnt[w[k]]==1) sum++; } void del(int k) { if(--cnt[w[k]]==0) sum--; } void work(int o,int k) { if(c[o].pos>=q[k].ql&&c[o].pos<=q[k].qr) { if (--cnt[w[c[o].pos]]==0) sum--; if (++cnt[c[o].val]==1) sum++; } swap(c[o].val,w[c[o].pos]); } bool cmp(query a,query b) { if (a.ql/num!=b.ql/num) return a.ql/num<b.ql/num; if (a.qr/num!=b.qr/num) return a.qr/num<b.qr/num; return a.t<b.t; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=m;i++) { char opt=get(); if (opt=='Q') { q[++cntq].t=cntc; q[cntq].ql=read(); q[cntq].qr=read(); q[cntq].id=cntq; } else { c[++cntc].pos=read(); c[cntc].val=read(); } } num=ceil(exp((log(n)+log(cntq))/3));; sort(q+1,q+cntq+1,cmp); int L=0,R=0,now=0; for(int i=1;i<=m;i++) { int ql=q[i].ql,qr=q[i].qr; while (L<ql) del(L++); while (R>qr) del(R--); while (L>ql) add(--L); while (R<qr) add(++R); while (now<q[i].t) work(++now,i); while (now>q[i].t) work(now--,i); ans[q[i].id]=sum; } for(int i=1;i<=cntq;i++) printf("%dn",ans[i]); return 0; }
|
近期评论