2过不去，1,3压线。

#include<bits/stdc++.h>
#define add0 nxt[x]=1,o[++oc]=oper(0,x,0)
#define adtag o[++oc]=oper(2,b,0),tag[b]=1
#define repsum o[++oc]=oper(1,b,sum[b])
#define link(x,y) o[++oc]=oper(0,x,nxt[x]),o[++oc]=oper(0,y,nxt[y]),nxt[y]=nxt[x]=y-x+1
using namespace std;
const int maxn=3e5+5,maxm=666,blk=483,blk2=1766;
typedef long long ll;
char __buf[1<<19],*__p1,*__p2;
#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<19,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
inline int read() {
	int __x=0;
	char __c=getchar();
	while(__c<'0'||__c>'9') __c=getchar();
	while(__c>='0'&&__c<='9') {
		__x=__x*10+__c-'0';
		__c=getchar();
	}
	return __x;
}
inline char pc(const char ch,const bool bj) {
	static char buf[1<<16],*p1=buf,*p2=buf+(1<<16);
	return ((bj)||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
void print(const ll x) {
	if(x>9)print(x/10);
	pc(x%10^48,0);
}
inline void printnum(const ll x,const char ch) {
	print(x),pc(ch,0);
}
struct quest {
	int l,r,x,id;
	quest(const int L,const int R,const int X,const int i) {
		l=L,r=R,x=X,id=i;
	}
};
struct node {
	int x,y,t;
	node(const int X,const int Y,const int T) {
		x=X,y=Y,t=T;
	}
};
struct oper {
	char op;
	int x,y;
	oper() {}
	oper(const char o,const int X,const int Y) {
		op=o,x=X,y=Y;
	}
} o[maxn*3];
typedef vector<node>::iterator iter;
typedef vector<quest>::iterator ite;
vector<node> p[maxm];
vector<quest> q[maxm];
int a[maxn],rk[maxn],cnt[maxn],n,m,oc,l[maxm],r[maxm],sum[maxm];
short bel[maxn],nxt[maxn],sn,sm;
bool tag[maxm],pd[maxn];
char op[maxn];
ll ans[maxn],c2[maxn];
bool cmp(const quest a,const quest b) {
	return a.x<b.x;
}
inline void merge(const int x) {
//	cout<<x<<' '<<a[x]<<endl;
	const int b=bel[x],lb=l[b],rb=r[b],lsx=x+nxt[x+1],prx=x-nxt[x-1];
	const bool lspd=lsx==x,prpd=prx==x;
	if(x==lb) {
		if(lspd)add0;
		else if(lsx==rb)adtag;
		else repsum,sum[b]-=c2[lsx-x],link(x,lsx);
	} else if(x==rb) {
		if(prpd)add0;
		else if(prx==lb)adtag;
		else repsum,sum[b]-=c2[x-prx],link(prx,x);
	} else {
		if(prpd&&lspd)add0,repsum,sum[b]++;
		else if(lspd) {
			if(prx!=lb)repsum,sum[b]+=x-prx+1;
			link(prx,x);
		} else if(prpd) {
			if(lsx!=rb)repsum,sum[b]+=lsx-x+1;
			link(x,lsx);
		} else {
			if(prx==lb&&lsx==rb)adtag;
			else {
				repsum;
				if(prx==lb)sum[b]-=c2[lsx-x];
				else if(lsx==rb)sum[b]-=c2[x-prx];
				else sum[b]-=c2[x-prx]+c2[lsx-x],sum[b]+=c2[lsx-prx+1];
				link(prx,lsx),add0;
			}
		}
	}
}
inline void replace(const int cas) {
	while(oc>cas) {
		const char op=o[oc].op;
		if(!op)nxt[o[oc].x]=o[oc].y;
		else if(op==1)sum[o[oc].x]=o[oc].y;
		else tag[o[oc].x]=0;
		oc--;
	}
}
ll getans(const int lx,const int ry) {
	ll w=0;
	int cc=0;
	const int x=bel[lx],y=bel[ry];
//	for(register int i=1;i<=n;i++)cout<<bool(nxt[i]);
//	puts("");
	if(x==y) {
		if(tag[x])cc=ry-lx+1;
		else for(register int i=lx; i<=ry; i++)nxt[i]?cc++:(w+=c2[cc],cc=0);
		return w+c2[cc];
	}
	if(tag[x])cc+=r[x]-lx+1;
	else for(register int i=lx; i<=r[x]; i++)nxt[i]?cc++:(w+=c2[cc],cc=0);
	for(register short i=x+1; i<=y-1; i++) {
//		cout<<(int)tag[i]<<' '<<nxt[l[i]]<<' '<<sum[i]<<' '<<nxt[r[i]]<<endl;
		if(tag[i])cc+=r[i]-l[i]+1;
		else w+=c2[cc+nxt[l[i]]]+sum[i],cc=nxt[r[i]];
	}
	if(tag[y])cc+=ry-l[y]+1;
	else for(register int i=l[y]; i<=ry; i++)nxt[i]?cc++:(w+=c2[cc],cc=0);
	return w+c2[cc];
}
int main() {
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	int x,y;
	n=read(),m=read(),sn=n/blk+(n%blk!=0),sm=m/blk2+(m%blk2!=0);
	for(register short i=1; i<=sn; i++)l[i]=(i-1)*blk+1,r[i]=min(i*blk,n);
	for(register int i=1; i<=n; i++)a[i]=read(),bel[i]=(i-1)/blk+1,c2[i]=(ll)i*(i+1)/2;
	for(register int i=1; i<=m; i++) {
		op[i]=read(),x=read(),y=read();
		const int bk=(i-1)/blk2+1;
		if(op[i]==1)p[bk].insert(p[bk].end(),node(x,y,i));
		else q[bk].insert(q[bk].end(),quest(x,y,read(),i));
	}
	for(register short i=1; i<=sm; i++) {
//		cerr<<i<<endl;
		sort(q[i].begin(),q[i].end(),cmp),reverse(p[i].begin(),p[i].end());
		memset(cnt,0,sizeof(cnt));
		for(register int j=1; j<=n; j++)cnt[a[j]]++;
		for(register int j=1; j<=n; j++)cnt[j]+=cnt[j-1];
		for(register int j=1; j<=n; j++)rk[cnt[a[j]]--]=j;
		register int lst=1;
		const iter fs=p[i].begin(),ls=p[i].end();
		for(register iter it=fs; it!=ls; it++)pd[it->x]=1;
//		puts("###");
//		for(register int j=1;j<=sn;j++)cout<<(int)tag[j]<<' '<<pre[j]<<' '<<sum[j]<<' '<<suf[j]<<endl;
		for(register ite it=q[i].begin(); it!=q[i].end(); it++) {
//			puts("------");
//			cout<<it->l<<' '<<it->r<<' '<<it->x<<' '<<it->id<<endl;
			const int x=it->x,id=it->id;
			while(a[rk[lst]]<=x&&lst<=n) {
				if(!pd[rk[lst]])merge(rk[lst]);
				lst++;
			}
			const int cas=oc;
			if(fs!=ls) {
//				puts("*");
				for(register iter tmp=fs; tmp!=ls; tmp++) {
					if(tmp->t>id)continue;
					if(!pd[tmp->x])continue;
					if(tmp->y<=x)merge(tmp->x);
					pd[tmp->x]=0;
				}
//				puts("*");
				for(register iter tmp=fs; tmp!=ls; tmp++) {
					if(tmp->t<id)break;
					if(!pd[tmp->x])continue;
					if(a[tmp->x]<=x)merge(tmp->x);
					pd[tmp->x]=0;
				}
				for(register iter tmp=fs; tmp!=ls; tmp++)pd[tmp->x]=1;
			}
//			puts("***");
			ans[id]=getans(it->l,it->r);
			replace(cas);
		}
		replace(0);
		for(register iter it=fs; it!=ls; it++) {
			if(!pd[it->x])continue;
			a[it->x]=it->y,pd[it->x]=0;
		}
	}
	for(register int i=1; i<=m; i++)if(op[i]==2)printnum(ans[i],'\n');
	pc(0,1);
}