做法：带修莫队
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
typedef __uint128_t ULLL;
static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
inline void pc(const char &ch){
if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
*pw++=ch;
}
#define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
struct FastMod{
FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
ULL reduce(ULL a){
ULL q=(ULL)((ULLL(m)*a)>>64);
ULL r=a-q*b;
return r>=b?r-b:r;
}
ULL b,m;
}HPOP(10);
struct QIO{
char ch;
int st[40];
inline void read(int &x){
x=0,ch=gc;
while(!isdigit(ch))ch=gc;
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
}
inline void write(int a){
do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
while(st[0])pc(st[st[0]--]^48);
pc('\n');
}
}qrw;
}
using namespace FastIo;
#define NUMBER1 1000000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
int n,m,a[NUMBER1+5],ans[NUMBER1+5],mq(0),mc(0),fk,sum(0),cnt[NUMBER1+5];
struct ASK{
int id,l,r,t;
bool operator<(const ASK &A)const{
int L=l/fk,AL=A.l/fk,R=r/fk,AR=A.r/fk;
return (L!=AL)?(L<AL):((R!=AR)?(R<AR):(t<A.t));
}
ASK(int id=0,int l=0,int r=0,int t=0):id(id),l(l),r(r),t(t){}
}q[NUMBER1+5];
struct CHANGE{
int p,color;
CHANGE(int p=0,int color=0):p(p),color(color){}
}c[NUMBER1+5];
inline void add(const int &data){
P(cnt[data]);
if(cnt[data]==1)P(sum);
else if(cnt[data]==2)--sum;
}
inline void del(const int &data){
--cnt[data];
if(!cnt[data])--sum;
else if(cnt[data]==1)P(sum);
}
signed main(){
int x,y,t(0),op;
qrw.read(n);
qrw.read(m);
fione_i(1,n)qrw.read(a[i]);
fione_i(1,m){
qrw.read(op);
qrw.read(x);
qrw.read(y);
if(op==2)mq++,q[mq]=ASK(mq,x+1,y+1,mc);
else c[++mc]=CHANGE(x+1,y);
}
fk=pow((double)n*std::max(1,mc),1.0/3),x=1,y=0;
std::sort(q+1,q+1+mq);
fione_i(1,mq){
while(y<q[i].r)add(a[++y]);
while(y>q[i].r)del(a[y--]);
while(x<q[i].l)del(a[x++]);
while(x>q[i].l)add(a[--x]);
while(t<q[i].t){
P(t);
if(c[t].p<=y&&c[t].p>=x){
del(a[c[t].p]);
add(c[t].color);
}
std::swap(a[c[t].p],c[t].color);
}
while(t>q[i].t){
if(c[t].p<=y&&c[t].p>=x){
del(a[c[t].p]);
add(c[t].color);
}
std::swap(a[c[t].p],c[t].color);
--t;
}
ans[q[i].id]=sum;
}
fione_i(1,mq)qrw.write(ans[i]);
fsh;
exit(0);
return 0;
}