MnZn刚学OI，求卡常

#include<bits/stdc++.h>
#pragma optimize("Ofast")
#pragma optimize("unroll-loops")
#pragma optimize("inline")
#pragma optimize("-ffast-math")
#pragma optimize("-falign-loops")
#pragma optimize("-funroll-loops")
#pragma optimize("-fstrict-aliasing")
using namespace std;
const int B=800;
inline int read(){
	int u=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		u=(u<<3)+(u<<1)+(c^'0'); c=getchar();
	}
	return u;
}
inline void write(const long long &u){
	if(u<10) putchar(u^48);
	else write(u/10),putchar((u%10)^48);
}
struct opt{
	int tp,x,v,l,r;
};
opt w[B+5];
opt myopt[B+5];//备份修改操作
int a[300005],n,q;//维护原序列
int b[300005];//离散化后序列
int to[300005];//离散化对应
int h[300005];//每个数在哪个块中
//关键点的定义：对于修改，x为关键点；对于查询，l-1,r为关键点
struct block{//保证只有块尾可能是关键点
	int l,r;//对应原序列位置
	int c[B+5];//离散化后第一个>x的对应原序列位置（没有为r+1）
	int d[B+5];//离散化后最后一个>x的对应原序列位置（没有为l-1）
	int e[B+5];//离散化后除块尾最后一个>x的对应原序列位置（没有为l-1）
	int ans[B+5];//块内答案
};
block s[B*3+5];
int d[B*3+5],m;//m为块数
int x[B+5],k;//k为值域
int fir[B+5],fol[300005];//用于排序，会将值相同的数倒序插入qwq
int pre[300005],nxt[300005];//b中前一个严格大于b[i]的位置、后一个大于等于b[i]的位置
int tmp[300005],sz;//维护单调栈
//int ps[30005];
//long long ps2[300005];
void print(int id){
	cerr<<"这是第"<<id<<"块的信息：\n";
	cerr<<"对应原序列：["<<s[id].l<<","<<s[id].r<<"]\n";
	cerr<<"离散化值：";
	for(int i=s[id].l;i<=s[id].r;i++) cerr<<b[i]<<' '; cerr<<'\n';
	for(int i=1;i<=k;i++){
		cerr<<"c["<<i<<"]="<<s[id].c[i]<<"\td["<<i<<"]="<<s[id].d[i]<<"\t";
		cerr<<"e["<<i<<"]="<<s[id].e[i]<<"\tans["<<i<<"]="<<s[id].ans[i]<<"\n";
	}
	cerr<<'\n';
}
int tim1,tim2,tim3,tim4,tim21,tim22,tim221,tim222;
void solve(){
	const bool step1=1,step2=1,step3=1,step4=1;
//	step1: 离散化
	if(step1){
		clock_t st=clock();
		m=k=0;
		for(int i=1;i<=q;i++){
			if(w[i].tp==1) d[++m]=w[i].x;
			else{
				if(w[i].l!=1) d[++m]=w[i].l-1; d[++m]=w[i].r; x[++k]=w[i].x;
			}
		}
		x[++k]=n;
		sort(x+1,x+1+k); k=unique(x+1,x+1+k)-x-1;
		for(int i=1;i<=k;i++){
			for(int j=x[i];j>x[i-1];j--){
				to[j]=i;
			}
		}
		for(int i=n;i>0;i-=n/B) d[++m]=i;
		sort(d+1,d+m+1);
		m=unique(d+1,d+m+1)-d-1;
		for(int i=1;i<=m;i++) s[i].l=d[i-1]+1,s[i].r=d[i];
		for(int i=1;i<=m;i++){
			for(int j=s[i].l;j<=s[i].r;j++){
				h[j]=i;
			}
		}
		for(int i=1;i<=n;i++){
			b[i]=to[a[i]];
		}
		for(int i=1;i<=q;i++) if(w[i].tp==1) w[i].v=to[w[i].v]; else w[i].x=to[w[i].x];
		clock_t ed=clock();
		tim1+=ed-st;
	}
//	cerr<<"b序列："; for(int i=1;i<=n;i++) cerr<<b[i]<<' '; cerr<<'\n';
//	cerr<<"step1: done.\n";
//	step2: 预处理块内信息
	if(step2){
		clock_t st=clock();
		sz=0;
		tmp[sz]=0; b[0]=0x3f3f3f3f;
		for(int i=1;i<=n;i++){
			while(b[tmp[sz]]<=b[i]) nxt[tmp[sz]]=i,sz--;
			pre[i]=tmp[sz]; tmp[++sz]=i;
		}
		for(int i=1;i<=sz;i++) nxt[tmp[i]]=n+1;
//		sz=0;
//		tmp[sz]=n+1; b[n+1]=0x3f3f3f3f;
//		for(int i=n;i>=1;i--){
//			while(b[tmp[sz]]<b[i]) sz--;
//			nxt[i]=tmp[sz]; tmp[++sz]=i;
//		}
		clock_t mid=clock();
		for(int i=1;i<=m;i++){
//			clock_t ss1=clock();
			/*
			for(int j=0;j<=k+1;j++) s[i].c[j]=s[i].r+1,s[i].e[j]=s[i].d[j]=s[i].l-1;
			for(int j=s[i].l;j<s[i].r;j++){
				if(s[i].c[b[j]-1]==s[i].r+1) s[i].c[b[j]-1]=j;
				s[i].d[b[j]-1]=j; s[i].e[b[j]-1]=j;
			}
			if(s[i].c[b[s[i].r]-1]==s[i].r+1) s[i].c[b[s[i].r]-1]=s[i].r;
			s[i].d[b[s[i].r]-1]=s[i].r;
			
			for(int j=k;j>=1;j--){
				if(s[i].c[j-1]>s[i].c[j]) s[i].c[j-1]=s[i].c[j];
				if(s[i].d[j-1]<s[i].d[j]) s[i].d[j-1]=s[i].d[j];
				if(s[i].e[j-1]<s[i].e[j]) s[i].e[j-1]=s[i].e[j];
			}
			*/
			int pos=0;
			for(int j=s[i].l;j<=s[i].r;j++){
				while(pos<b[j]) s[i].c[pos++]=j;
			}
			while(pos<=k+1) s[i].c[pos++]=s[i].r+1;
			pos=0;
			for(int j=s[i].r-1;j>=s[i].l;j--){
				while(pos<b[j]) s[i].e[pos++]=j;
			}
			while(pos<=k+1) s[i].e[pos++]=s[i].l-1;
//			pos=0;
//			for(int j=s[i].r;j>=s[i].l;j--){
//				while(pos<b[j]) s[i].d[pos++]=j;
//			}
//			while(pos<=k+1) s[i].d[pos++]=s[i].l-1;
			memcpy(s[i].d,s[i].e,k+2<<2);
			for(int j=b[s[i].r]-1;~j;j--){
				s[i].d[j]=s[i].r;
			}
//			clock_t ss2=clock();
			memset(fir,0,k+3<<2);
			for(int j=s[i].l;j<=s[i].r;j++){
				fol[j]=fir[b[j]]; fir[b[j]]=j;
			}
			memset(s[i].ans,0,k+3<<2);
			int nans=(s[i].r-s[i].l+1)*(s[i].r-s[i].l+2)/2;
			for(int j=k+1;j>1;j--){
				for(int c=fir[j];c;c=fol[c]){
					nans-=(min(nxt[c],s[i].r+1)-c)*(c-max(pre[c],s[i].l-1));
				}
				s[i].ans[j-1]=nans;
			}
//			clock_t ss3=clock();
//			tim221+=ss2-ss1; tim222+=ss3-ss2;
		}
		clock_t ed=clock();
		tim2+=ed-st;
		tim21+=mid-st; tim22+=ed-mid;
	}
//	for(int i=1;i<=m;i++) print(i);
//	cerr<<"step2: done.\n";
//	step3: 处理询问
    if(step3){
		clock_t st=clock();
		for(int i=1;i<=q;i++){
			if(w[i].tp==1){
				int x=w[i].x,v=w[i].v;
				int u=h[x];
				for(int j=k;j>=b[x];j--){
					s[u].ans[j]-=s[u].r-s[u].d[j];
				}
				memcpy(s[u].d,s[u].e,k+2<<2);
				for(int j=1;j<v;j++) s[u].d[j]=x;
				for(int j=k;j>=v;j--){
					s[u].ans[j]+=s[u].r-s[u].d[j];
				}
//				for(int j=v-1;s[u].c[j]==s[u].r+1;j--) s[u].c[j]=x;
//				for(int j=v;)
				if(v>b[x]){
					for(int j=1;j<v;j++){
						if(s[u].c[j]==s[u].r+1){
							s[u].c[j]=x;
						}
					}
				}else{
					for(int j=v;j<=k;j++){
						if(s[u].c[j]==x){
							s[u].c[j]=s[u].r+1;
						}
					}
				}

				b[x]=v;
//				cerr<<"1 "<<x<<" "<<v<<" done.\n";
//				print(u);
			}else{
				int l=h[w[i].l],r=h[w[i].r],x=w[i].x;
				int pos=w[i].l-1;//上一个大数的位置
				long long ans=0;
				for(int j=l;j<=r;j++){
                    ans+=s[j].ans[x];
					ans+=1ll*(s[j].c[x]-s[j].l)*(s[j].l-pos-1);
					if(s[j].d[x]!=s[j].l-1) pos=s[j].d[x];
				}
//				cerr<<"2 "<<w[i].l<<' '<<w[i].r<<' '<<w[i].x<<" done.\n";
				write(ans); putchar(10);
			}
		}
		clock_t ed=clock();
		tim3+=ed-st;
	}
//	cerr<<"step3: done.\n";
//	step4: 实际更新
	if(step4){
		clock_t st=clock();
		for(int i=1;i<=q;i++){
			if(myopt[i].tp==1){
				a[myopt[i].x]=myopt[i].v;
			}
		}
		clock_t ed=clock();
		tim4+=ed-st;
	}
//	cerr<<"step4: done.\n\n";
}
int main(){
//	for(int i=1;i<=30000;i++) ps[i]=i*(i+1)/2;
//	for(int i=1;i<=300000;i++) ps2[i]=1ll*i*(i+1)/2;
//	freopen("1.in","r",stdin); freopen("1.out","w",stdout);
	int m;
	n=read(); m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	while(m--){
		q++; w[q].tp=read();
		if(w[q].tp==1) w[q].x=read(),w[q].v=read(),myopt[q]=w[q];
		else w[q].l=read(),w[q].r=read(),w[q].x=read(),myopt[q]={0,0,0,0,0};
		if(m%B==0){
			solve(); q=0;
		}
	}
	cerr<<"tim1: "<<tim1*1.0/CLOCKS_PER_SEC<<'\n';
	cerr<<"tim2: "<<tim2*1.0/CLOCKS_PER_SEC<<'\n';
	cerr<<"tim21: "<<tim21*1.0/CLOCKS_PER_SEC<<'\n';
	cerr<<"tim22: "<<tim22*1.0/CLOCKS_PER_SEC<<'\n';
//	cerr<<"tim221: "<<tim221*1.0/CLOCKS_PER_SEC<<'\n';
//	cerr<<"tim222: "<<tim222*1.0/CLOCKS_PER_SEC<<'\n';
	cerr<<"tim3: "<<tim3*1.0/CLOCKS_PER_SEC<<'\n';
	cerr<<"tim4: "<<tim4*1.0/CLOCKS_PER_SEC<<'\n';
	return 0;
}