写的是 这个做法

目前34pts,自己构造的数据在[3.5,4.5]秒之间。

代码比较丑

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define MAXB 2005
typedef long long ll;
int b[MAXN];
int *a,n,m,N,B;
ll cnt[MAXB];
#define mp(x) ((x)/B)
#define ct(x) ((ll)(x)*((x)+1)/2)
int L[MAXB],R[MAXB],Lc[MAXB],Rc[MAXB];
int lst[MAXB],nxt[MAXB];
int q[MAXN],qq[MAXB];
pair<int, int> c[MAXB];
int pd;
void modify(const int x,const int v){
	q[a[x]]--,qq[a[x]>>9]--;
	a[x]=v;
	q[a[x]]++,qq[a[x]>>9]++;
	pd=1;
	for(int i=1;i<=N;++i){
		if(c[i].second==x){
			pair<int, int> tmp=c[i];tmp.first=v;
			for(int j=i+1;j<=N;++j)
				c[j-1]=c[j];
			for(int j=1;j<=N;++j)
				if(j==N||c[j]>tmp){
					for(int k=N;k>=j;--k)
						c[k]=c[k-1];
					c[j]=tmp;
					return;
				}
		}
	}
}
void query(const int LL,const int RR,const int x,int &len,ll &ans){
	if(LL==1&&RR==N){
		if(pd){
			for(int i=1;i<=N;++i)
				L[i]=R[i]=cnt[i]=Lc[i]=Rc[i]=0;
			int i=1;
			for(;i+7<=N;i+=8){
				lst[i]=i-1;
				lst[i+1]=i;
				lst[i+2]=i+1;
				lst[i+3]=i+2;
				lst[i+4]=i+3;
				lst[i+5]=i+4;
				lst[i+6]=i+5;
				lst[i+7]=i+6;
			}
			for(;i<=N;++i)lst[i]=i-1;
			i=1;
			for(;i+7<N;i+=8){
				nxt[i]=i+1;
				nxt[i+1]=i+2;
				nxt[i+2]=i+3;
				nxt[i+3]=i+4;
				nxt[i+4]=i+5;
				nxt[i+5]=i+6;
				nxt[i+6]=i+7;
				nxt[i+7]=i+8;
			}
			for(;i<N;++i)nxt[i]=i+1;nxt[N]=0;
			for(int i=1;i<=N;++i){
				cnt[i]=cnt[i-1];
				{
					const int x=c[i].second,T=i;
					L[x]=R[x]=x;cnt[T]++;
					int tl=lst[x],tn=nxt[x];
					if(tl&&L[tl]){
						cnt[T]-=ct(R[tl]-L[tl]+1);
						if(L[lst[tl]]==L[tl])
							tl=lst[tl];
					}
					else tl=x;
					if(tn&&R[tn]){
						cnt[T]-=ct(R[tn]-L[tn]+1);
						if(R[nxt[tn]]==R[tn])
							tn=nxt[tn];
					}
					else tn=x;
					if(tl!=x||tn!=x){
						cnt[T]+=ct(R[tn]-L[tl]+1)-1;
						nxt[tl]=tn,lst[tn]=tl;
						R[tl]=R[tn],L[tn]=L[tl];
					}
					Lc[T]=R[1],Rc[T]=L[N]?N-L[N]+1:0;
				}
			}
			pd=0;
		}
		int T=0,i=0;
		for(;i+7<(x>>9);i+=8){
			T+=qq[i];
			T+=qq[i+1];
			T+=qq[i+2];
			T+=qq[i+3];
			T+=qq[i+4];
			T+=qq[i+5];
			T+=qq[i+6];
			T+=qq[i+7];
		}
		for(;i<(x>>9);++i)T+=qq[i];
		i=(x>>9)<<9;
		for(;i+7<=x;i+=8){
			T+=q[i];
			T+=q[i+1];
			T+=q[i+2];
			T+=q[i+3];
			T+=q[i+4];
			T+=q[i+5];
			T+=q[i+6];
			T+=q[i+7];
		}
		for(;i<=x;++i)T+=q[i];
		ll now=cnt[T]-ct(Lc[T])-ct(Rc[T]);
		if(Lc[T]==N)
			return len+=N,void();
		ans+=now+ct(len+Lc[T]);
		len=Rc[T];
		return;
	}
	else if(LL==1){
		int lst=len;len=0;
		for(int i=1;i<=RR;++i)
			a[i]>x?ans+=ct(lst),lst=0:lst++;
		ans+=ct(lst);
		return;
	}
	else if(RR==N){
		int lst=0;
		for(int i=LL;i<=N;++i)
			a[i]>x?ans+=ct(lst),lst=0:lst++;
		len=lst;
		return;
	}
	else{
		int lst=len;
		for(int i=LL;i<=RR;++i)
			a[i]>x?ans+=ct(lst),lst=0:lst++;
		ans+=ct(lst);
		return;
	}
}
int opt[MAXN],LL[MAXN],RR[MAXN],vv[MAXN];
int len[MAXN];ll ans[MAXN];
#define gc()(xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<20,stdin),xS==xTT)?0:*xS++)
#define pc(x)(p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
using namespace std;typedef long long ll;typedef double db;typedef long double ld;typedef unsigned long long ull;typedef unsigned int ui;char xch,xB[1<<20],*xS=xB,*xTT=xB,obuf[1000000],*p3=obuf;
int read(){char ch=gc();int x=0;while(ch<'0'||ch>'9')ch=gc();while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}return x;}static char cc[20];
void pt(ll x){ int len=0;if(!x)pc('0');if(x<0)x=-x,pc('-');while(x)cc[len++]=x%10+'0',x/=10;while(len--)pc(cc[len]);}
int main(){
	cin>>n>>m;B=1500;
	for(int i=1;i<=n;++i)
		b[i]=read();
	for(int i=1;i<=m;++i){
		opt[i]=read(),LL[i]=read();
		if(opt[i]==1)vv[i]=read();
		else RR[i]=read(),vv[i]=read();
	}
	for(int i=0;i<=mp(n);++i){
		a=b+i*B;N=(i==mp(n)?n%B:B);
		{
			for(int i=1;i<=N;++i)
				L[i]=R[i]=cnt[i]=Lc[i]=Rc[i]=0;
			lst[1]=0;for(int i=2;i<=N;++i)lst[i]=i-1;
			nxt[N]=0;for(int i=1;i<N;++i)nxt[i]=i+1;
			for(int i=1;i<=N;++i)
				q[a[i]]++,qq[a[i]>>9]++,c[i]={a[i],i};
			sort(c+1,c+N+1);
			for(int i=1;i<=N;++i){
				cnt[i]=cnt[i-1];
				{
					const int x=c[i].second,T=i;
					L[x]=R[x]=x;cnt[T]++;
					int tl=lst[x],tn=nxt[x];
					if(tl&&L[tl]){
						cnt[T]-=ct(R[tl]-L[tl]+1);
						if(L[lst[tl]]==L[tl])
							tl=lst[tl];
					}
					else tl=x;
					if(tn&&R[tn]){
						cnt[T]-=ct(R[tn]-L[tn]+1);
						if(R[nxt[tn]]==R[tn])
							tn=nxt[tn];
					}
					else tn=x;
					if(tl!=x||tn!=x){
						cnt[T]+=ct(R[tn]-L[tl]+1)-1;
						nxt[tl]=tn,lst[tn]=tl;
						R[tl]=R[tn],L[tn]=L[tl];
					}
					if(R[1])Lc[T]=R[1];else Lc[T]=0;
					if(L[N])Rc[T]=N-L[N]+1;else Rc[T]=0;
				}
			}
		}
		pd=0;
		int nl=i*B+1,nr=(i+1)*B;
		for(int j=1;j<=m;++j){
			if(opt[j]==1){
				if(nl<=LL[j]&&nr>=LL[j])
					modify(LL[j]-i*B,vv[j]);
			}
			else{
				int xl=max(LL[j],nl),xr=min(RR[j],nr);
				if(xl<=xr)query(xl-i*B,xr-i*B,vv[j],len[j],ans[j]);
			}
		}
		for(int j=1;j<=N;++j)q[a[j]]--,qq[a[j]>>9]--;
	}
	for(int i=1;i<=m;++i)
		if(opt[i]==2)pt(ans[i]+ct(len[i])),pc('\n');
 	fwrite(obuf,p3-obuf,1,stdout);
}

救救孩子吧卡两天了