萌新码风较丑请见谅

//敗者の言葉です
#include<bits/stdc++.h>
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE];
	char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33&&ch!=EOF)
	template<typename T> inline T read() {
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return false;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		return s * w;
	}
	template<typename T> inline void read(T &s) {
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		s *= w;
	}
	inline void read(char &s) {
		while (s = getchar(), isspace(s));
	}
	inline void read(char *s) {
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return;
		while (!isspace(ch)) *s++ = ch, ch = getchar();
		*s = '\000';
	}
	template<typename T> inline void print(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x % 10 + 48);
	}
	inline void print(char x) {
		putchar(x);
	}
	inline void print(char *x) {
		while (*x) putchar(*x++);
	}
	inline void print(const char *x) {
		for (int i = 0; x[i]; i++) putchar(x[i]);
	}
#ifdef _GLIBCXX_STRING
	inline bool read(std::string& s) {
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (!isspace(ch)) s += ch, ch = getchar();
		return true;
	}
	inline void print(std::string x) {
		for (int i = 0, n = x.size(); i < n; i++)
			putchar(x[i]);
	}
#endif//string
	template<typename T, typename... T1> inline bool read(T& a, T1&... other) {
		return read(a) && read(other...);
	}
	template<typename T, typename... T1> inline void print(T a, T1... other) {
		print(a);
		print(other...);
	}
	struct Fast_IO {
		~Fast_IO() {
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
	}io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
		return read(b),io;
	}
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
		return print(b),io;
	}
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
#define MAXN 330000
#define MAXQ 660
#define il inline
using namespace std;
namespace wzk{
	int n,q,maxn;
	int a[MAXN];
	struct qry{
		int op,l,r,x,y;
	}qr[MAXN];
	int b,m,left[MAXQ],right[MAXQ],bel[MAXN];
	int b_val,m_val,left_val[MAXQ],right_val[MAXQ],bel_val[MAXN];
	struct node{
		int w,id;
	}s[MAXN];
	il bool cmp(node x,node y){
		return x.w<y.w;
	}
	il void build(){
		b=sqrt(n),m=ceil(1.0*n/b);
		for(int i=1;i<=m;i++){
			left[i]=right[i-1]+1,right[i]=min(n,i*b);
			for(int j=left[i];j<=right[i];j++) bel[j]=i,s[j].w=a[j],s[j].id=j;
			sort(s+left[i],s+right[i]+1,cmp);
		}
		b_val=min(maxn,650),m_val=ceil(1.0*maxn/b_val);
		for(int i=1;i<=m_val;i++){
			left_val[i]=right_val[i-1]+1,right_val[i]=min(maxn,i*b_val);
			for(int j=left_val[i];j<=right_val[i];j++) bel_val[j]=i;
		}
	}
	long long ans[MAXQ][MAXQ],c[MAXN];
	int oth[MAXN];//The other side
	int pre[MAXQ][MAXQ],suf[MAXQ][MAXQ];
	il long long get(int l,int r){
		if(l>r) return 0ll;
		return c[r-l+1];
	}
	il void init(int p){
		int l=left[p],r=right[p];
		for(int i=l;i<=r;i++) oth[i]=0;
		oth[l-1]=oth[l+1]=oth[r-1]=oth[r+1]=0;
		for(int i=1;i<=r-l+1;i++){
			int po=l+i-1,to=0,to2=0;
			int id=s[po].id;
			pre[p][i]=pre[p][i-1],suf[p][i]=suf[p][i-1];
			if(oth[id-1]&&oth[id+1]){
				to=oth[id-1],to2=oth[id+1];
				oth[to]=to2,oth[to2]=to;
				if(id-1!=to) oth[id-1]=0;
				if(id+1!=to2) oth[id+1]=0;
				ans[p][i]=ans[p][i-1]-get(to,id-1)-get(id+1,to2)+get(to,to2);
				if(to2==r) suf[p][i]=r-to+1;
				if(to==l) pre[p][i]=to2-l+1;
			}else if(oth[id-1]){
				to=oth[id-1];
				oth[id]=to,oth[to]=id;
				if(id-1!=to) oth[id-1]=0;
				ans[p][i]=ans[p][i-1]-get(to,id-1)+get(to,id);
				if(id==r) suf[p][i]=r-to+1;
				if(to==l) pre[p][i]=pre[p][i-1]+1;
			}else if(oth[id+1]){
				to=oth[id+1];
				oth[id]=to,oth[to]=id;
				if(id+1!=to) oth[id+1]=0;
				ans[p][i]=ans[p][i-1]-get(id+1,to)+get(id,to);
				if(id==l) pre[p][i]=to-l+1;
				if(to==r) suf[p][i]=suf[p][i-1]+1;
			}else{
				oth[id]=id,ans[p][i]=ans[p][i-1]+1;
				if(id==l) pre[p][i]=1;
				if(id==r) suf[p][i]=1;
			}
		}
	}
	long long rans[MAXN];
	int fst[MAXN],va[MAXN],sum[MAXN];
	int nxt1[MAXQ],nxt2[MAXN];//1:第i个(值域)块后的后继(值域)块 2:第i个下标所属(值域)块内后继
	int rk[MAXN],kth[MAXN],la[MAXN];
	il void solve(int p){
		int lef=left[p],rig=right[p];
		init(p);
		// memset(va,0,sizeof(va));
		// memset(sum,0,sizeof(sum));
		for(int i=1;i<=maxn;i++) va[i]=0;
		for(int i=1;i<=m_val;i++) sum[i]=0;
		for(int i=1;i<=maxn;i++) rk[i]=0;
		for(int i=lef;i<=rig;i++) va[a[i]]++,sum[bel_val[a[i]]]++;
		for(int i=maxn;i>=1;i--) if(va[i]) fst[bel_val[i]]=i;
		for(int i=m_val,have=0;i>=1;i--){
			nxt1[i]=have;
			if(sum[i]) have=i;
			for(int j=right_val[i],hv=0;j>=left_val[i];j--){
				nxt2[j]=hv;
				if(va[j]) hv=j;
			}
		}
		for(int i=lef;i<=rig;i++){
			kth[i-lef+1]=s[i].w;
			if(!rk[s[i].w]) rk[s[i].w]=i-lef+1;
		}
		for(int i=1;i<=q;i++){
			int op=qr[i].op,l=qr[i].l,r=qr[i].r,x=qr[i].x,y=qr[i].y;
			if(op==1){
				if(x>rig||x<lef) continue;
				int pos=0,val=0;
				for(int j=lef;j<=rig;j++) rk[s[j].w]=0;
				for(int j=lef;j<=rig;j++){
					if(x==s[j].id){
						pos=j;
						break;
					}
				}
				val=s[pos].w;
				a[x]=y;
				s[pos].w=y;
				while(s[pos].w<s[pos-1].w&&pos>lef) swap(s[pos],s[pos-1]),pos--;
				while(s[pos].w>s[pos+1].w&&pos<rig) swap(s[pos],s[pos+1]),pos++;
				for(int j=lef;j<=rig;j++){
					kth[j-lef+1]=s[j].w;
					if(!rk[s[j].w]) rk[s[j].w]=j-lef+1;
				}
				init(p);
				if(va[val]==1){
					for(int j=left_val[bel_val[val]];j<=right_val[bel_val[val]];j++) if(nxt2[j]==val) nxt2[j]=nxt2[val];
					if(sum[bel_val[val]]==1) for(int j=1;j<=bel_val[val];j++) if(nxt1[j]==bel_val[val]) nxt1[j]=nxt1[bel_val[val]];
				}
				va[val]--,sum[bel_val[val]]--;
				fst[bel_val[val]]=0;
				for(int j=left_val[bel_val[val]];j<=right_val[bel_val[val]];j++){
					if(va[j]){
						fst[bel_val[val]]=j;
						break;
					}
				}
				if(!va[y]){
					int to=kth[rk[y]+1];
					if(to>right_val[bel_val[y]]) to=0;
					for(int j=left_val[bel_val[y]];j<y;j++) if(nxt2[j]==to) nxt2[j]=y;
					if(!sum[bel_val[y]]) for(int j=1;j<bel_val[y];j++) if(nxt1[j]==nxt1[bel_val[y]]) nxt1[j]=bel_val[y];
				}
				va[y]++,sum[bel_val[y]]++;
				fst[bel_val[y]]=0;
				for(int j=left_val[bel_val[y]];j<=right_val[bel_val[y]];j++){
					if(va[j]){
						fst[bel_val[y]]=j;
						break;
					}
				}
			}else{
				if(l>rig||r<lef) continue;
				int lp=bel[l],rp=bel[r],last=0;
				if(lp==rp){
					last=l-1;
					for(int j=l;j<=r;j++) if(a[j]>x) rans[i]+=get(last+1,j-1),last=j;
					rans[i]+=get(last+1,r);
					continue;
				}
				if(p==lp){
					last=l-1;
					for(int j=l;j<=right[lp];j++) if(a[j]>x) rans[i]+=get(last+1,j-1),last=j;
					rans[i]+=get(last+1,right[lp]);
					for(int j=right[lp];j>=l;j--){
						if(a[j]<=x) la[i]=j;
						else break;
					}
					if(!la[i]) la[i]=right[lp]+1;
				}else if(p==rp){
					// cerr<<"##################"<<i<<' '<<la[i]<<'\n';
					int lla=la[i],j=0;
					for(j=left[rp];a[j]<=x&&j<=r;j++);
					rans[i]=rans[i]-get(lla,left[rp]-1)+get(lla,j-1);
					last=j-1;
					// cerr<<last<<'\n';
					for(;j<=r;j++) if(a[j]>x) rans[i]+=get(last+1,j-1),last=j;
					rans[i]+=get(last+1,r);
				}else{
					// cerr<<"@@@\n";
					// cerr<<rans[i]<<'\n';
					int tmp=0,pp=0,t=la[i];
					if(nxt2[x]) tmp=nxt2[x];
					else if(nxt1[bel_val[x]]) tmp=fst[nxt1[bel_val[x]]];
					if(tmp) pp=rk[tmp]-1;
					else pp=right[p]-left[p]+1;
					rans[i]=rans[i]-get(t,lef-1)-get(lef,lef+pre[p][pp]-1)+get(t,lef+pre[p][pp]-1)+ans[p][pp];
					if(suf[p][pp]!=right[pp]-left[pp]+1) la[i]=rig-suf[p][pp]+1;
					// cerr<<rans[i]<<'\n';
				}
			}
		}
	}
	int main(){
		// freopen(".in","r",stdin);
		// freopen(".out","w",stdout);
		cin>>n>>q;
		for(int i=1;i<=n;i++) cin>>a[i],c[i]=1ll*i*(i+1)>>1,maxn=max(maxn,a[i]);
		for(int i=1;i<=q;i++){
			cin>>qr[i].op;
			if(qr[i].op==1) cin>>qr[i].x>>qr[i].y,maxn=max(maxn,qr[i].y);
			else cin>>qr[i].l>>qr[i].r>>qr[i].x,maxn=max(maxn,qr[i].x);
		}
		build();
		// cerr<<n<<' '<<maxn<<'\n';
		// cerr<<b<<' '<<m<<"  "<<b_val<<' '<<m_val<<'\n';
		for(int i=1;i<=m;i++) solve(i);
		for(int i=1;i<=q;i++) if(qr[i].op==2) cout<<rans[i]<<'\n';
		return 0;
	}
}
int main(){
	return wzk::main();
}
//Good night.

是这样的，第 112 行的 b 块长只能在恰好等于 sqrt(n) 即 547 时正确，可以卡过，但是取其他值都 WA 了。

悬2关。