操作分块+序列分块

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define fc(x) (1ll*(x)*((x)+1)/2)
namespace io{
    const ll BUFSIZE=1<<22;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline ll read(){
        ll res=0;bool neg=false;char ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)ch=getch();
        if(ch=='-')neg=true,ch=getch();
        while(isdigit(ch))res=res*10+(ch-'0'),ch=getch();
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)flush();
    }
    inline void write(ll res){
        char q[25];ll top;
        if(res<0)putch('-'),res=-res;
        if(res==0)putch('0');           
        top=0;
        while(res)q[top++]=res%10+'0',res/=10;
        while(top--)putch(q[top]);
    }
}
using namespace io;
using namespace std;
const int N=3e5+10;
int sum[N],n,m,op,l,r,x,y,a[N],bl,tot,c[N],st[N],ed[N],pos[N],S,tot1,tot2,tq1,tq2;
ll ans[N];
bitset<N> b,vis,bb,bbb;
vector<int> tg[N];
struct que{int l,r,x,t;}q1[N],q2[N];
bool cmp(que a,que b){return a.x<b.x;}
pair<int,int> v1[N*3],v2[N*3];
void init(){
	bl=sqrt(n*3/4),tot=(n-1)/bl+1;
	for(int i=1;i<=n;i++)pos[i]=(i-1)/bl+1;
	for(int i=1;i<=tot;i++)st[i]=(i-1)*bl+1,ed[i]=i*bl;
	ed[tot]=n;
}
void revoke(){
	reverse(v1+1,v1+tot1+1);
	for(int i=1;i<=tot1;i++)c[v1[i].first]=v1[i].second;
	for(int i=1;i<=tot2;i++)sum[v2[i].first]-=v2[i].second;
	tot1=tot2=0;
}
void do1(int x,int k){
	int y=0;
	v1[++tot1]={x,c[x]};
	v1[++tot1]={c[x+1],c[c[x+1]]};
	y-=fc(c[x+1]-x);
	int r=c[x+1],l=x;
	c[l]=r;
	c[r]=l;
	y+=fc(r-l+1);
	sum[k]+=y;
	v2[++tot2]={k,y};
} 
void do2(int x,int k){
	int y=0;
	v1[++tot1]={x,c[x]};
	v1[++tot1]={c[x-1],c[c[x-1]]};
	y-=fc(x-c[x-1]);
	int r=x,l=c[x-1];
	c[l]=r;
	c[r]=l;
	y+=fc(r-l+1);
	sum[k]+=y;
	v2[++tot2]={k,y};
}
void do3(int x,int k){
	v1[++tot1]={x,c[x]};
	c[x]=x;
	sum[k]++;
	v2[++tot2]={k,1};
}
void do4(int x,int k){
	int y=0;
	v1[++tot1]={c[x+1],c[c[x+1]]};
	v1[++tot1]={c[x-1],c[c[x-1]]};
	v1[++tot1]={x,c[x]};
	y-=fc(x-c[x-1]);
	y-=fc(c[x+1]-x);
	int r=c[x+1],l=c[x-1];
	c[r]=l;
	c[l]=r;
	c[x]=x;
	y+=fc(r-l+1);
	sum[k]+=y;
	v2[++tot2]={k,y};
}
void turn(int x){
	int k=pos[x];
	if(x==st[k]){
		if(c[x+1])do1(x,k);
		else do3(x,k);
	}else if(x==ed[k]){
		if(c[x-1])do2(x,k);
		else do3(x,k);
	}else{
		if(c[x+1]&&c[x-1])do4(x,k);
		else if(c[x+1])do1(x,k);
		else if(c[x-1])do2(x,k);
		else do3(x,k);
	}
}
int get(int l,int r){
	int ans=0;
	for(int i=l;i<=r;i++){
		if(!c[i])continue;
		int j=i;
		while(j<=r&&c[j])j++;
		ans+=fc(j-i);
		i=j-1;
	}
	return ans;
}
ll ask(int l,int r){
	int L=pos[l],R=pos[r];
	ll ans=0;
	if(L==R)ans=get(l,r);
	else{
		int last=max(l,c[ed[L]]?c[ed[L]]:ed[L]+1);
		ans=get(l,ed[L]);
		if(c[ed[L]])ans-=fc(ed[L]-last+1);
		for(int i=L+1;i<=R-1;i++){
			if(c[st[i]]==ed[i])continue;
			ans+=fc((c[st[i]]?c[st[i]]:ed[i-1])-last+1);
			ans+=sum[i];
			if(c[st[i]])ans-=fc(c[st[i]]-st[i]+1);
			if(c[ed[i]])ans-=fc(ed[i]-c[ed[i]]+1);
			last=c[ed[i]]?c[ed[i]]:ed[i]+1;
		}
		ans+=get(st[R],r);
		ans+=fc(min((c[st[R]]?c[st[R]]:ed[R-1]),r)-last+1);
		if(c[st[R]])ans-=fc(min(r,c[st[R]])-st[R]+1);
	}
	return ans;
}
void solve(){
	sort(q2+1,q2+tq2+1,cmp);
	reverse(q1+1,q1+tq1+1);
	for(int i=1;i<=tq1;i++)vis[q1[i].l]=true;
	for(int i=1;i<=n;i++)if(!vis[i])tg[a[i]].push_back(i);
	int j=1;
	for(int w=1;w<=tq2;w++){
		que i=q2[w];
		while(j<=i.x){
			for(int x:tg[j])turn(x);
			j++;
		}
		tot1=0,tot2=0;
		for(int o=1;o<=tq1;o++){
			que k=q1[o];
			if(k.t>i.t||bb[k.l])continue;
			bb[k.l]=true;
			if(k.r<=i.x)turn(k.l);
		}
		for(int o=1;o<=tq1;o++){
			que k=q1[o];
			if(bb[k.l]||bbb[k.l])continue;
			bbb[k.l]=true;
			if(a[k.l]<=i.x)turn(k.l);
		}
		for(int o=1;o<=tq1;o++){
			que k=q1[o];
			bbb[k.l]=bb[k.l]=false;
		}
		ans[i.t]=ask(i.l,i.r);
		revoke();
	}
	reverse(q1+1,q1+tq1+1);
	for(int i=1;i<=tq1;i++)a[q1[i].l]=q1[i].r;
	for(int i=1;i<=n;i++)tg[i].clear();
	memset(sum,0,sizeof(sum));
	memset(c,0,sizeof(c));
	vis=0,tq1=0,tq2=0;
}
signed main(){
	n=read(),m=read();
	init();
	for(int i=1;i<=n;i++)a[i]=read();
	S=sqrt(m*14);
	for(int i=1;i<=m;i++){
		op=read();
		if(op==1)x=read(),y=read(),q1[++tq1]={x,y,0,i};
		else l=read(),r=read(),x=read(),q2[++tq2]={l,r,x,i},b[i]=true;
		if(tq1+tq2==S)solve();
	}
	solve();
	for(int i=1;i<=m;i++)if(b[i])write(ans[i]),putch('\n');
	flush();
}