我写的是 这个做法。

但它 TLE 了，分数在 60 左右浮动。

能不能帮我看看怎么卡常。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> void chkmax(T& x,T y){if(y>x)x=y;}
template<typename T> void chkmin(T& x,T y){if(y<x)x=y;}
const int MAXN=3e5+5;

namespace IO{
	char ibuf[1<<20],*ip1=0,*ip2=0;
	char gc(){if(ip1==ip2)ip1=ibuf,ip2=ibuf+fread(ibuf,1,1<<20,stdin);return ip1==ip2?EOF:*ip1++;}
	char obuf[1<<20],*op1=obuf,*op2=obuf+(1<<20);
	void flush(){fwrite(obuf,1,op1-obuf,stdout);}
	void pc(char c){*op1++=c;if(op1==op2)flush(),op1=obuf;}
	struct ioo{ioo(){}~ioo(){flush();}}ioo;
};
using namespace IO;
int read(){
	int ret=0,t=1;char c=gc();
	while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')t=-1,c=gc();
	while(c>='0'&&c<='9')ret=ret*10+c-'0',c=gc();return ret*t;
}
void print(ull x){
	if(x==0){pc('0');return;}if(x<0)pc('-'),x=-1;
	static char buf[100],bufl;while(x)buf[++bufl]=x%10,x/=10;
	while(bufl)pc('0'+buf[bufl--]);
}

inline ull qwq(int x){return 1ull*x*(x+1)/2;}

int N,M,Blo,a[MAXN],A[MAXN];
struct query{int op,x,y,z;}q[MAXN];int cl[MAXN];ull ans[MAXN];
int lb[MAXN],rb[MAXN],blo[MAXN];

struct dsu{
	int fa[MAXN],siz[MAXN];
	void init(int l,int r){for(int i=l;i<=r;++i)fa[i]=i,siz[i]=1;}
	int get(int x){if(fa[x]!=x)fa[x]=get(fa[x]);return fa[x];}
	void merge(int x,int y){
		x=get(x),y=get(y);if(x==y)return;
		if(siz[x]>siz[y])swap(x,y);
		fa[x]=y,siz[y]+=siz[x];
	}
}dsu;

int sorted[MAXN],rk[MAXN];
bool cmp(int i,int j){return a[i]<a[j];}
int llen[MAXN],rlen[MAXN],sum[MAXN];

struct ds{
	int buc[MAXN],val[MAXN],valb[MAXN];
	void ins(int pos,int k){
		buc[pos]+=k;int fir=0;
		for(int i=lb[blo[pos]];i<=rb[blo[pos]];++i){if(buc[i])fir=i;val[i]=fir;}
		if(!fir)fir=valb[blo[pos]];
		for(int i=blo[pos]+1;i<=blo[N];++i){
			valb[i]=fir;
			if(val[rb[i]])break;
		}
	}
	int qry(int pos){return val[pos]?val[pos]:valb[blo[pos]];}
	void clear(){for(int i=1;i<=N;++i)buc[i]=val[i]=0;for(int i=1;i<=blo[N];++i)valb[i]=0;}
}ds;

void rebuild(int cur){
	static bool buc[MAXN];
	dsu.init(lb[cur],rb[cur]);
	int cursum=0;
	for(int j=lb[cur];j<=rb[cur];++j){
		int id=sorted[j];
		if(buc[id-1])cursum-=dsu.get(lb[cur])!=dsu.get(id-1)?qwq(dsu.siz[dsu.get(id-1)]):0,dsu.merge(id-1,id);
		if(buc[id+1])cursum-=dsu.get(rb[cur])!=dsu.get(id+1)?qwq(dsu.siz[dsu.get(id+1)]):0,dsu.merge(id,id+1);
		buc[id]=1,cursum+=dsu.get(lb[cur])!=dsu.get(id)&&dsu.get(rb[cur])!=dsu.get(id)?qwq(dsu.siz[dsu.get(id)]):0;
		llen[j]=buc[lb[cur]]?dsu.siz[dsu.get(lb[cur])]:0,rlen[j]=buc[rb[cur]]?dsu.siz[dsu.get(rb[cur])]:0,sum[j]=cursum;
	}
	for(int j=lb[cur];j<=rb[cur];++j)buc[j]=0;
}

int main(){
	N=read(),M=read(),Blo=sqrt(N);
	for(int i=1;i<=N;++i)a[i]=read(),A[i]=a[i];
	for(int i=1;i<=N;++i)blo[i]=(i-1)/Blo+1;
	for(int i=1;i<=blo[N];++i)lb[i]=(i-1)*Blo+1,rb[i]=min(N,i*Blo);
	for(int i=1;i<=M;++i){
		q[i].op=read();
		if(q[i].op==1)q[i].x=read(),q[i].y=read();
		else q[i].x=read(),q[i].y=read(),q[i].z=read();
	}
	for(int cur=1;cur<=blo[N];++cur){
		for(int i=1;i<=N;++i)a[i]=A[i],rk[i]=0;
		for(int i=lb[cur];i<=rb[cur];++i)sorted[i]=i;
		sort(sorted+lb[cur],sorted+rb[cur]+1,cmp),rebuild(cur);
		ds.clear();
		for(int i=lb[cur];i<=rb[cur];++i)rk[a[sorted[i]]]=i,ds.ins(a[i],1);
		for(int i=1;i<=M;++i){
			if(q[i].op==1){
				if(lb[cur]<=q[i].x&&q[i].x<=rb[cur]){
					for(int j=lb[cur];j<=rb[cur];++j)rk[a[j]]=0;
					int j;for(j=lb[cur];j<=rb[cur];++j)if(sorted[j]==q[i].x)break;
					for(;j<rb[cur];++j)sorted[j]=sorted[j+1];sorted[rb[cur]]=0;
					ds.ins(a[q[i].x],-1),a[q[i].x]=q[i].y,ds.ins(a[q[i].x],1);
					for(j=lb[cur];j<rb[cur];++j)if(a[sorted[j]]>=q[i].y)break;
					for(int k=rb[cur];k>j;--k)sorted[k]=sorted[k-1];sorted[j]=q[i].x;
					for(int j=lb[cur];j<=rb[cur];++j)rk[a[sorted[j]]]=j;
					rebuild(cur);
				}
			}else{
				if(q[i].x<=lb[cur]&&rb[cur]<=q[i].y){
					int po=rk[ds.qry(q[i].z)];
					if(llen[po]==rb[cur]-lb[cur]+1)cl[i]+=llen[po];
					else{
						cl[i]+=llen[po],ans[i]+=qwq(cl[i]),cl[i]=0;
						ans[i]+=sum[po],cl[i]=rlen[po];
					}
				}else{
					int ll=1,rr=0;
					if(lb[cur]<=q[i].x&&q[i].y<=rb[cur])ll=q[i].x,rr=q[i].y;
					else if(lb[cur]<q[i].x&&q[i].x<=rb[cur])ll=q[i].x,rr=rb[cur];
					else if(lb[cur]<=q[i].y&&q[i].y<rb[cur])ll=lb[cur],rr=q[i].y;
					for(int j=ll;j<=rr;++j){
						if(a[j]<=q[i].z)++cl[i];
						else ans[i]+=qwq(cl[i]),cl[i]=0;
					}
				}
			}
		}
	}
	for(int i=1;i<=M;++i)if(q[i].op==2){
		ans[i]+=qwq(cl[i]);
		print(ans[i]),pc('\n');
	}
	return 0;
}