裸的带修莫队。
在Sort时如果左右区间都在同一块中,就按询问的修改的先后Sort。
对于每次查询判断向前或向后修改。
当size为N*2/3时据说是最优。O(N^(3/5))。
code:
/**************************************************************
Problem: 2120
User: yekehe
Language: C++
Result: Accepted
Time:884 ms
Memory:5652 kb
****************************************************************/
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
inline char tc(void){
static char fl[],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
int read()
{
char c;while(c=tc(),c<''||c>'');
int x=c-'';while(c=tc(),c>=''&&c<='')x=(x<<)+(x<<)+c-'';
return x;
}
int N,M,size,a[],D[],Be[],ans,sum[],A[],l,r,t;
struct Query{int l,r,tim,id;}Q[];int Qs;
struct Change{int x,bef,to;}C[];int Cs;
int cmp(Query x,Query y){
return Be[x.l]==Be[y.l]?
(Be[x.r]==Be[y.r]?x.tim<y.tim:x.r<y.r)
:x.l<y.l;
}//CMP函数
void re(int x,int d){
sum[x]+=d;
if(!sum[x]&&d<)ans--;
if(sum[x]==&&d>)ans++;
}
int ct(int x,int y){
if(l<=x&&x<=r)re(a[x],-),re(y,);
a[x]=y;
}
int main()
{
N=read(),M=read();
for(int i=;i<=N;i++)a[i]=read(),D[i]=a[i];
int x,y;char c;
for(int i=;i<=M;i++){
while(c=tc(),c!='Q'&&c!='R');
x=read(),y=read();
if(c=='Q')Q[++Qs]=(Query){x,y,Cs,Qs};
else C[++Cs]=(Change){x,D[x],y},D[x]=y;
}
size=pow(N,0.66666);
for(int i=;i<=N;i++)
Be[i]=(i-)/size+;
sort(Q+,Q+Qs+,cmp);
l=,r=,t=;
for(int i=;i<=Qs;i++){
while(t<Q[i].tim)t++,ct(C[t].x,C[t].to);//向后修改
while(t>Q[i].tim)ct(C[t].x,C[t].bef),t--;//向前修改
while(l<Q[i].l)re(a[l],-),l++;
while(l>Q[i].l)re(a[--l],);
while(r<Q[i].r)re(a[++r],);
while(r>Q[i].r)re(a[r],-),r--;
A[Q[i].id]=ans;
}
for(int i=;i<=Qs;i++)
printf("%d\n",A[i]);
return ;
}