98pts求助

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int head[maxn],nxt[maxn],tt,shu[maxn],qi[maxn],zh[maxn],sj,h[maxn],nt[maxn],fy[maxn],rr,sum[maxn],yy[maxn];
int n,m,a[maxn],B1,B,tp,tot,pre[maxn],suf[maxn],b[maxn],ss[maxn],L,R,ll,zg,op,cc;
long long ans,anss[maxn],S;
bool now[maxn],vis[maxn];
struct IO {
	static const int Size = (1 << 21);
	char buf[Size], *p1, *p2; int st[105], Top;
	~IO() {clear();}
	inline void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}
	inline char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}
	inline void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}
	inline IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}
	template <typename T> inline IO &operator >> (T &x) {
		x = 0; bool f = 0; char ch = gc();
		while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}
		while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		f ? x = -x : 0; return *this;
	}
	inline IO &operator << (const char c) {pc(c); return *this;}
	template <typename T> inline IO &operator << (T x) {
		if(x < 0) pc('-'), x = -x;
		do st[++st[0]] = x % 10, x /= 10; while(x);
		while(st[0]) pc('0' + st[st[0]--]);
		return *this;
	}
	inline IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;
struct edge{
	int x,y;
}xiu[maxn];
struct node{
	int l,r,x,id,t;
}wen[maxn];
inline void solve(){
	for(int i=1;i<=n;i++){
		vis[i]=1;
		now[i]=0;
		sum[i]=0;
	}
	tt=0;
	for(int i=1;i<=tp;i++){
		vis[xiu[i].x]=0;
	}
	sj=0;
	for(int i=1;i<=tot;i++){
		sj=max(sj,wen[i].x);
		nxt[i]=head[wen[i].x];
		head[wen[i].x]=i;
	}
	for(int i=1;i<=n;i++){
		pre[i]=suf[i]=i;
		if(!vis[i]){
			ss[++tt]=i;
			fy[i]=tt;
		}
		else if(a[i]<=sj){
			nt[i]=h[a[i]];
			h[a[i]]=i;
		}
	}
	for(int i=1;i<=sj;i++){
		for(int j=h[i];j;j=nt[j]){
			now[j]=1;
			if(now[j-1]&&shu[j-1]==shu[j]){
				sum[shu[j]]-=(suf[j-1]-pre[j-1]+1)*(suf[j-1]-pre[j-1]+2);
				pre[j]=pre[j-1];
				suf[pre[j-1]]=j;
			}
			if(now[j+1]&&shu[j+1]==shu[j]){
				sum[shu[j]]-=(suf[j+1]-pre[j+1]+1)*(suf[j+1]-pre[j+1]+2);
				pre[suf[j+1]]=pre[j];
				suf[pre[j]]=suf[j+1];
			}
			sum[shu[j]]+=(suf[pre[j]]-pre[suf[j]]+1)*(suf[pre[j]]-pre[suf[j]]+2);
		}
		h[i]=0;
		for(int j=head[i];j;j=nxt[j]){
			cc++;
			for(int k=1;k<=tt;k++){
				b[k]=(a[ss[k]]<=i);
			}
			for(int k=1;k<=wen[j].t;k++){
				b[fy[xiu[k].x]]=(xiu[k].y<=i);
			}
			ans=0;
			for(int k=1;k<=tt;k++){
				if(!b[k]||yy[k]==cc||ss[k]<wen[j].l||ss[k]>wen[j].r){
					continue;
				}
				L=ss[k],R=ss[k];
				S=0;
				while(L>wen[j].l&&(now[L-1]||b[fy[L-1]])){
					ll=pre[L-1],rr=L-1;
					if(!fy[rr]){
						S+=max(0,min(rr,wen[j].r)-max(ll,wen[j].l)+1);
					}
					else{
						ans-=S*(S+1);
						S=0;
					}
					L=ll;
				}
				ans-=S*(S+1);
				S=0;
				while(R<wen[j].r&&(now[R+1]||b[fy[R+1]])){
					ll=R+1,rr=suf[ll];
					if(!fy[ll]){
						S+=max(0,min(rr,wen[j].r)-max(ll,wen[j].l)+1);
					}
					else{
						yy[fy[ll]]=cc;
						ans-=S*(S+1);
						S=0;
					}
					R=rr;
				}
				ans-=S*(S+1);
				S=max(0,min(R,wen[j].r)-max(L,wen[j].l)+1);
				ans+=S*(S+1);
			}
			S=0;
			if(shu[wen[j].l]==shu[wen[j].r]){
				for(int k=wen[j].l;k<=wen[j].r;k++){
					if(now[k]){
						S++;
					}
					else{
						ans+=S*(S+1);
						S=0;
					}
				}
				ans+=S*(S+1);
			}
			else{
				for(int k=wen[j].l;k<=zh[shu[wen[j].l]];k++){
					if(now[k]){
						S++;
					}
					else{
						ans+=S*(S+1);
						S=0;
					}
				}
				for(int k=shu[wen[j].l]+1;k<shu[wen[j].r];k++){
					if(now[qi[k]]&&suf[qi[k]]==zh[k]){
						S+=zh[k]-qi[k]+1;
					}
					else{
						if(now[qi[k]]){
							S=S+suf[qi[k]]-pre[qi[k]]+1;
							ans+=S*(S+1);
							S=suf[qi[k]]-pre[qi[k]]+1;
							ans-=S*(S+1);
						}
						else{
							ans+=S*(S+1);
						}
						ans+=sum[k];
						if(now[zh[k]]){
							S=suf[zh[k]]-pre[zh[k]]+1;
							ans-=S*(S+1);
						}
						else{
							S=0;
						}
					}
				}
				for(int k=qi[shu[wen[j].r]];k<=wen[j].r;k++){
					if(now[k]){
						S++;
					}
					else{
						ans+=S*(S+1);
						S=0;
					}
				}
				ans+=S*(S+1);
			}
			anss[wen[j].id]=ans;
		}
		head[i]=0;
	}
	for(int i=1;i<=tot;i++){
		fout<<(anss[i]>>1)<<'\n';
	}
	for(int i=1;i<=tp;i++){
		a[xiu[i].x]=xiu[i].y;
		fy[xiu[i].x]=0;
		b[i]=0;
	}
	tot=0;
	tp=0;
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	fin>>n>>m;
	for(int i=1;i<=n;i++){
		fin>>a[i];
	}
	B=sqrt(0.81*n);
	for(int l=1,r;l<=n;l=r+1){
		r=min(l+B-1,n);
		zg++;
		qi[zg]=l;
		zh[zg]=r;
		for(int i=l;i<=r;i++){
			shu[i]=zg;
		}
	}
	B1=sqrt(14*m);
	for(int i=1;i<=m;i++){
		fin>>op;
		if(op==1){
			tp++;
			fin>>xiu[tp].x>>xiu[tp].y;
			if(tp==B1){
				solve();
			}
		}
		else{
			tot++;
			fin>>wen[tot].l>>wen[tot].r>>wen[tot].x;
			wen[tot].t=tp;
			wen[tot].id=tot;
		}
	}
	solve();
	return 0;
}