#1 #2 过不去，写的分散层叠。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+5,S=350;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<22],*p1=buf,*p2=buf;
int read() {
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct node {
	int v,nxt1,nxt2;
	node(){}
	node(int _v,int _nxt1,int _nxt2){v=_v;nxt1=_nxt1;nxt2=_nxt2;}
	bool operator < (const node &q)const{return v<q.v;}
}*t[(N/S+1)<<2],tmp1[S+2],tmp2[S+2];
struct pii {
	int v,i;
	pii(){}
	pii(int _v,int _i){v=_v;i=_i;}
	bool operator < (const pii &q)const{return v<q.v;}
}b[N];
node SSS[N*4],*nw;
int n,m,a[N],bel[N];
int L[N/S+2],R[N/S+2],lx[N/S+2][S+2],rx[N/S+2][S+2],len[(N/S+1)<<2];
LL val[N/S+2][S+2],C[N];
int pre[N],suf[N];
LL calc(int x) {return C[x];}
void rebuild(int nw) {
	for(int i=L[nw];i<=R[nw];++i)pre[i]=i-1,suf[i]=i+1;
	lx[nw][0]=L[nw];rx[nw][0]=R[nw];
	for(int o=1,pos;o<=R[nw]-L[nw]+1;++o) {// b[i].v<= <b[i+1].v
		pos=b[L[nw]+o-1].i;
		lx[nw][o]=lx[nw][o-1];rx[nw][o]=rx[nw][o-1];val[nw][o]=val[nw][o-1];
		int pr=pre[pos],sf=suf[pos];
		if(pr<L[nw])lx[nw][o]=sf;
		else val[nw][o]-=calc(pos-pr-1);
		if(sf>R[nw])rx[nw][o]=pr;
		else val[nw][o]-=calc(sf-pos-1);
		if(pr>=L[nw]&&sf<=R[nw])val[nw][o]+=calc(sf-pr-1);
		suf[pr]=sf;pre[sf]=pr;
	}
}
#define ls (id<<1)
#define rs (id<<1|1)
#define mid ((l+r)>>1)
void pushup(int id) {
	int tA=0,tB=0;
	for(int i=3;i<=len[ls];i+=3)tmp1[++tA]=node(t[ls][i].v,i,0);
	for(int i=3;i<=len[rs];i+=3)tmp2[++tB]=node(t[rs][i].v,0,i);
	int i=1,j=1,k=0;
	while(i<=tA&&j<=tB) {
		if(tmp1[i]<tmp2[j])t[id][++k]=node(tmp1[i].v,tmp1[i].nxt1,tmp2[j].nxt2),++i;
		else t[id][++k]=node(tmp2[j].v,tmp1[i].nxt1,tmp2[j].nxt2),++j;
	}
	while(i<=tA)t[id][++k]=node(tmp1[i].v,tmp1[i].nxt1,0),++i;
	while(j<=tB)t[id][++k]=node(tmp2[j].v,0,tmp2[j].nxt2),++j;
}
void build(int id,int l,int r) {
	if(l==r) {
		t[id]=nw;
		len[id]=R[l]-L[l]+1;nw+=len[id]+1;
		for(int i=L[l];i<=R[l];++i)t[id][i-L[l]+1]=node(b[i].v,i,0);
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	len[id]=len[ls]/3+len[rs]/3;
	t[id]=nw;nw+=len[id]+1;
	pushup(id);
}
void upt(int id,int l,int r,int ps) {
	if(l==r) {
		for(int i=L[l];i<=R[l];++i)t[id][i-L[l]+1]=node(b[i].v,i,0);
		return;
	}
	if(ps<=mid)upt(ls,l,mid,ps);
	else upt(rs,mid+1,r,ps);
	pushup(id);
}
LL Q(int l,int r,int x,int &lst) {
	LL res=0;
	for(int i=l;i<=r;++i)
		if(a[i]>x) {
			res+=calc(i-lst-1);
			lst=i;
		}
	return res;
}
LL qry(int id,int l,int r,int x,int y,int k,int &lst,int nw) {
	if(!nw&&t[id][len[id]].v>=k)nw=len[id];
	while(nw&&t[id][nw-1].v>=k)--nw;
	LL res=0;
	if(l==r) {
		if(!nw)return 0;
		--nw;
		res+=calc(lx[l][nw]-lst-1)+val[l][nw];
		lst=rx[l][nw];
	}
	else {
		if(x<=mid)res+=qry(ls,l,mid,x,y,k,lst,t[id][nw].nxt1);
		if(y>mid)res+=qry(rs,mid+1,r,x,y,k,lst,t[id][nw].nxt2);
	}
	return res;
}
int main() {
//	freopen("1.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;++i)a[i]=read(),bel[i]=(i-1)/S+1,b[i]=pii(a[i],i),C[i]=1ll*i*(i-1)/2+1ll*i;
	for(int i=1;i<=bel[n];++i)L[i]=(i-1)*S+1,R[i]=i*S;R[bel[n]]=n;
	for(int i=1;i<=bel[n];++i) {
		sort(b+L[i],b+R[i]+1);
		rebuild(i);
	}
	nw=SSS;
	build(1,1,bel[n]); 
	for(int T=1;T<=m;++T) {
		int opt=read();
		if(opt==1) {
			int x=read(),y=read(),nw=bel[x];
			a[x]=y;
			for(int i=L[nw];i<=R[nw];++i) {
				if(b[i].i==x) {
					b[i].v=y;
					while(i<R[nw]&&b[i+1]<b[i])swap(b[i],b[i+1]),++i;
					while(i>L[nw]&&b[i]<b[i-1])swap(b[i],b[i-1]),--i;
					break;
				}
			}
			rebuild(nw);
			upt(1,1,bel[n],nw);
		}
		else {
			int l=read(),r=read(),x=read(),lst=l-1;
			LL res=0;
			if(bel[l]==bel[r])res=Q(l,r,x,lst);
			else {
				res+=Q(l,R[bel[l]],x,lst);
				if(bel[l]<bel[r]-1)res+=qry(1,1,bel[n],bel[l]+1,bel[r]-1,x+1,lst,0);
				res+=Q(L[bel[r]],r,x,lst);
			}
			printf("%lld\n",res+calc(r-lst));
		}
	}
	return 0;
}