人 傻 常 数 大

n=300000 m=300000 上跑了80多s，当场尬住

BallBall大佬帮帮孩子

code:

#include<cmath>
#include<bitset>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define ll long long
#define int long long
using namespace std;

//header part

const int maxn=900010;
void in(int &val){val=0;
	char c=getchar();while(!isdigit(c))c=getchar();
	while(isdigit(c))val=((val<<3)+(val<<1)+(c^48)),c=getchar();
}

//limits & basic function

//Data span

bool ischged[maxn];
int tc[maxn],c[maxn],s[maxn],ts[maxn];
int posseq[maxn],ptr,n,m;//sort subscript by val
ll ans[maxn];

	//Fake Union-Find-Set 

struct Union_Find_Set{
	int dat[maxn];
	int find(int x){return x==dat[x]?x:dat[x]=find(dat[x]);}
	void init(int n){for(int i=1;i<=n;i++)dat[i]=i;}
	void claer(){memset(dat,0,sizeof(dat));}
}ArrL,ArrR;

struct Bin_Stack{
	bool isin[maxn];
	int dat[maxn],tot;
	void push(int x){if(isin[x])return;isin[x]=1;dat[++tot]=x;}
	void pop(){isin[dat[tot--]]=0;}
	bool empty(){return tot==0;}
	int top(){return dat[tot];}
}Bin_L,Bin_R,Bin_c,Bin_tc;

struct poi{int p,v;};
struct stackx{
	poi dat[maxn];
	int tot;
	void push(poi x){dat[++tot]=x;}
	void pop(){--tot;}
	bool empty(){return tot==0;}
	poi top(){return dat[tot];}
};

struct Union_Find_Set_L_affiliated{
	int dat[maxn];
	int find(int x){
		if(dat[x]==0)dat[x]=ArrL.dat[x],Bin_L.push(x);
		return x==dat[x]?x:dat[x]=find(dat[x]);
	}
	void clear(){
		while(!Bin_L.empty()){dat[Bin_L.top()]=0;Bin_L.pop();}
	}
}tArrL;

struct Union_Find_Set_R_affiliated{
	int dat[maxn];
	int find(int x){
		if(dat[x]==0)dat[x]=ArrR.dat[x],Bin_R.push(x);
		return x==dat[x]?x:dat[x]=find(dat[x]);
	}
	void clear(){
		while(!Bin_R.empty()){dat[Bin_R.top()]=0;Bin_R.pop();}
	}
}tArrR;

int spnv[maxn];
//For each indivual block F(blc_i) storgs at the L edge 
struct Blocked_Dat{
	stackx Backx;
	ll blcq[610],blcv[maxn];
	void upd(int x,int nlen){
		blcq[spnv[x]]-=blcv[x];
		blcv[x]=nlen*(nlen+1)/2;
		blcq[spnv[x]]+=blcv[x];
	}
	void tupd(int x,int nlen){
		//Back_P.push(x);
		//Back_V.push(floor(sqrt(blcv[x]*2)));
		Backx.push((poi){x,(int)floor(sqrt(blcv[x]*2))});
		upd(x,nlen);
	}
	void Back(){
		while(!Backx.empty()){
			upd(Backx.top().p,Backx.top().v);
			Backx.pop();
		}
	}
	ll getval(int x,int y){
		ll ret=0;
		if(spnv[x]==spnv[y]){
			for(int i=x;i<=y;i++)ret+=blcv[i];
			return ret;
		}
		for(int i=x;spnv[i]==spnv[x];i++)ret+=blcv[i];
		for(int i=spnv[x]+1;i<=spnv[y]-1;i++)ret+=blcq[i];
		for(int i=y;spnv[i]==spnv[y];i--)ret+=blcv[i];
		return ret;
	}
	ll ask(int x,int y,int limx){//Attention :check tc[x],tc[y]
		#define C2(x) (1ll*x*(x+1)/2)
		int Fx=tArrL.find(x),Fy=tArrL.find(y);
		if(Fx==Fy){
			if(Fx==x&&!(ts[x]||s[x])){
				return 0;
			}
			//in a same span
			int len=y-x+1;
			return C2(len);
		}
		ll ret=getval(Fx+1,Fy-1);
		int Gx=tArrR.find(x);
		if(Fx!=Gx||ts[x]==1){
			int len=Gx-x+1;
			ret+=C2(len);
		}
		if(Fy!= y||ts[y]==1){
			int len=y-Fy+1;
			ret+=C2(len);
		}
		return ret;
		#undef C2
	}
	void clear(){
		memset(blcq,0,sizeof(blcq));
		memset(blcv,0,sizeof(blcv));
	}
}SF;//sum of F(i)

struct question{int l,r,v,x,id;}q[maxn];int cntq;
struct chg{int x,bf,af;}ch[maxn];int cntc;

//end of data & datd structure

bool cmp(const question x,const question y){return x.x<y.x;}
//Core Algorithm
//Need to do
	//modify(int x)->change a single point x -> ok
	//tmodify(int x)->temporary change a single point x -> ok
	//query(quest x)->get answer of question x -> ok
	//update(int x)->update zero/one seqence to x ->????
void modify(const int x){
	if(ischged[x])return ;
	s[x]=1;
	//int Llim=ArrL.find(x),Rlim=ArrR.find(x);->Llim===x&&Rlim===x;
	//Four cases : 0 x 0 ; 1 x 0 ; 0 x 1 ; 1 x 1 ;
	if(s[x-1]==0&&s[x+1]==0){
		//case 0 x 0;
		SF.upd(x,1);
		return ;
	}
	if(s[x-1]==1&&s[x+1]==0){
		//case 1 x 0;
		int Llim=ArrL.find(x-1),Rlim=x-1;
		int len=Rlim-Llim+1;
		ArrR.dat[Llim]=x;
		ArrR.dat[Rlim]=x;
		ArrL.dat[x]=Llim;
		SF.upd(Llim,len+1);
		return ;
	}
	if(s[x-1]==0&&s[x+1]==1){
		//case 0 x 1;
		int Llim=x+1,Rlim=ArrR.find(x+1);
		int len=Rlim-Llim+1;
		ArrL.dat[Rlim]=x;
		ArrL.dat[Llim]=x;
		ArrR.dat[x]=Rlim;
		SF.upd(x,len+1);
		SF.upd(Llim,0);
		return ;
	}
	if(s[x-1]==1&&s[x+1]==1){
		//case 1 x 1;
		int LLlim=ArrL.find(x-1),LRlim=x-1;
		int RLlim=x+1,RRlim=ArrR.find(x+1);
		int Llen=LRlim-LLlim+1;
		int Rlen=RRlim-RLlim+1;
		ArrR.dat[LLlim]=RRlim;
		ArrR.dat[LRlim]=RRlim;
		ArrL.dat[RLlim]=LLlim;
		ArrL.dat[RRlim]=LLlim;
		ArrR.dat[x]=RRlim;
		ArrL.dat[x]=LLlim;
		SF.upd(RLlim,0);
		SF.upd(LLlim,Rlen+Llen+1);
		return ;
	}
	return ;//Should not be executed
}

//tmodify is roughly same as modify , we can copy it and change some var name

void tmodify(const int x){
	//if(ifchged[x])return ;
	//int Llim=ArrL.find(x),Rlim=ArrR.find(x);->Llim===x&&Rlim===x;
	//Four cases : 0 x 0 ; 1 x 0 ; 0 x 1 ; 1 x 1 ;
	if(ts[x-1]==0&&ts[x+1]==0){
		//case 0 x 0;
		SF.tupd(x,1);
		return ;
	}
	if(ts[x-1]==1&&ts[x+1]==0){
		//case 1 x 0;
		int Llim=tArrL.find(x-1),Rlim=x-1;
		int len=Rlim-Llim+1;
		tArrR.dat[Llim]=x;Bin_R.push(Llim);
		tArrR.dat[Rlim]=x;Bin_R.push(Rlim);
		tArrL.dat[x]=Llim;Bin_L.push(x);
		SF.tupd(Llim,len+1);
		return ;
	}
	if(ts[x-1]==0&&ts[x+1]==1){
		//case 0 x 1;
		int Llim=x+1,Rlim=tArrR.find(x+1);
		int len=Rlim-Llim+1;
		tArrL.dat[Rlim]=x;Bin_L.push(Rlim);
		tArrL.dat[Llim]=x;Bin_L.push(Llim);
		tArrR.dat[x]=Rlim;Bin_R.push(x);
		SF.tupd(x,len+1);
		SF.tupd(Llim,0);
		return ;
	}
	if(ts[x-1]==1&&ts[x+1]==1){
		//case 1 x 1;
		int LLlim=tArrL.find(x-1),LRlim=x-1;
		int RLlim=x+1,RRlim=tArrR.find(x+1);
		int Llen=LRlim-LLlim+1;
		int Rlen=RRlim-RLlim+1;
		tArrR.dat[LLlim]=RRlim;Bin_R.push(LLlim);
		tArrR.dat[LRlim]=RRlim;Bin_R.push(LRlim);
		tArrL.dat[RLlim]=LLlim;Bin_L.push(RLlim);
		tArrL.dat[RRlim]=LLlim;Bin_L.push(RRlim);
		tArrR.dat[x]=RRlim;Bin_R.push(x);
		tArrL.dat[x]=LLlim;Bin_L.push(x);
		SF.tupd(RLlim,0);
		SF.tupd(LLlim,Rlen+Llen+1);
		return ;
	}
	return ;//Should not be executed
}

ll query(question &x){
	//int v=0;
	for(int i=1;i<=cntc;i++){
		int p=ch[i].x;
		//tc[p]=c[p];
		if(i<=x.v)tc[p]=ch[i].af,Bin_tc.push(p);
		else if(tc[p]==0)tc[p]=c[p],Bin_tc.push(p);
		//tc[p+1]=c[p+1];
		if(tc[p+1]==0&&ischged[p+1]==0)tc[p+1]=c[p+1],Bin_tc.push(p+1);
		//tc[p-1]=c[p-1];
		if(tc[p-1]==0&&ischged[p-1]==0)tc[p-1]=c[p-1],Bin_tc.push(p-1);
	}
//	while(v<cntc){
//		v++;
//		int p=ch[v].x;
//		//int nxt=v<=x.v?:ch[v].bf;
//		if(nxt>x.x)continue;
//		if(ts[p]==0)ts[p]=1,Bin_c.push(p);
//		if(ts[p-1]==0)ts[p-1]=s[p-1],Bin_c.push(p-1);
//		if(ts[p+1]==0)ts[p+1]=s[p+1],Bin_c.push(p+1);
//		tmodify(ch[v].x);
//	}
	for(int i=1;i<=cntc;i++){
		if(tc[ch[i].x]>x.x)continue;
		int p=ch[i].x;
		if(ts[p]||s[p])continue;
		if(ts[p]==0)ts[p]=1,Bin_c.push(p);
		if(ts[p-1]==0)ts[p-1]=s[p-1],Bin_c.push(p-1);
		if(ts[p+1]==0)ts[p+1]=s[p+1],Bin_c.push(p+1);
		tmodify(p);
	}
	if(ts[x.l]==0)ts[x.l]=s[x.l],Bin_c.push(x.l);
	if(ts[x.r]==0)ts[x.r]=s[x.r],Bin_c.push(x.r);
	ll ret=SF.ask(x.l,x.r,x.x);
	tArrL.clear();
	tArrR.clear();
	SF.Back();
	while(!Bin_c.empty()){ts[Bin_c.top()]=0;Bin_c.pop();}
	while(!Bin_tc.empty()){tc[Bin_tc.top()]=0;Bin_tc.pop();}
	return ret;
}

void init_posseq(){
	static int cnt[maxn];
	static int pcnt[maxn];
	static int maxx;
	memset(cnt,0,sizeof(cnt));
	maxx=0;
	for(int i=1;i<=n;i++)++cnt[c[i]],maxx=max(maxx,c[i]);
	for(int i=0;i<=maxx;i++)pcnt[i+1]=pcnt[i]+cnt[i];
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++)
		posseq[pcnt[c[i]]+cnt[c[i]]+1]=i,++cnt[c[i]];
	return ;
}

void solve(){
	init_posseq();
	ArrL.init(n);
	ArrR.init(n);
	SF.clear();
	memset(s,0,sizeof(s));
	memset(ischged,0,sizeof(ischged));ptr=1;
	for(int i=1;i<=cntc;i++)ischged[ch[i].x]=1;
	for(int i=1;i<=cntq;i++){
		while(c[posseq[ptr]]<=q[i].x&&ptr<=n)
			modify(posseq[ptr++]);	
		ans[q[i].id]=query(q[i]);
	}
	for(int i=1;i<=cntq;i++)printf("%lld\n",ans[i]);
	return ;
}

//mhtiroglA eroC (End of Core)

signed main(){
	freopen("P6578.in","r",stdin);
	freopen("P6578.out","w",stdout);
	in(n),in(m);
	const int blcl=ceil(sqrt(300000))+1;
	for(int i=1;i<=300000;i++)spnv[i]=(i-1)/blcl+1;
	for(int i=1;i<=n;i++)in(c[i]);
	//please adjust the parameter
	int spnx=ceil(pow(m,0.66666666666));
	while(m){
		cntc=cntq=0;
		for(int i=1;i<=min(spnx,m);i++){
			static int opt;
			in(opt);
			if(opt==1){
				++cntc;
				in(ch[cntc].x);
				in(ch[cntc].af);
				ch[cntc].bf=c[ch[cntc].x];
				c[ch[cntc].x]=ch[cntc].af;
			}
			else {
				++cntq;
				in(q[cntq].l);
				in(q[cntq].r);
				in(q[cntq].x);
				q[cntq].v=cntc;
				q[cntq].id=cntq;
			}
		}
		for(int i=cntc;i>=1;i--)c[ch[i].x]=ch[i].bf;
		sort(q+1,q+1+cntq,cmp);
		solve();
		for(int i=1;i<=cntc;i++)c[ch[i].x]=ch[i].af;
		m-=min(spnx,m);
	}
    return 0;
}