复杂度不知道哪里错了，全部 TLE /fad

求指出复杂度哪里挂了 QAQ

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
typedef long long ll;
const ll N=6e5+5,M=6e5+5;
int n,m,a[N],l1,l2;
struct U{int id,v;}c[N],b1[N],b2[N];
bool cmp1(U x,U y){return x.v<y.v;}
void msort(){
	int t1=1,t2=1,to=0;
	for(;t1<=l1||t2<=l2;)
		if(t1<=l1&&(t2>l2||b1[t1].v<b2[t2].v)){
			c[++to]=b1[t1];
			t1++;
		}
		else{
			c[++to]=b2[t2];
			t2++;
		}
}
struct ds{
	int head[N],tail[N],K,pos[N],L[N],R[N],top,pre[N],suf[N];
	bool vis[N];ll ans[N];
	struct node{int op,x;ll y;}stak[M];
	void rep(int las){
		while(top>las){
			if(stak[top].op==1) head[stak[top].x]=stak[top].y;
			if(stak[top].op==2) tail[stak[top].x]=stak[top].y;
			if(stak[top].op==3) pre[stak[top].x]=stak[top].y;
			if(stak[top].op==4) suf[stak[top].x]=stak[top].y;
			if(stak[top].op==5) vis[stak[top].x]=stak[top].y;
			if(stak[top].op==6) ans[stak[top].x]=stak[top].y;
			top--;
		}
	}
	void Pre(){
		K=sqrt(n);
		for(int i=1;i<=n;i++) pos[i]=(i-1)/K+1;
		for(int i=1;i<=n;i++) R[pos[i]]=i;
		for(int i=n;i;i--) L[pos[i]]=i;
	}
	void link(int x,int y){
		stak[++top]=(node){1,y,head[y]};
		stak[++top]=(node){2,x,tail[x]};
		head[y]=x,tail[x]=y;
	}
	ll gx(ll x){return x*(x+1)/2;}
	void change(int x){
		if(vis[x]) return ;
		int y1,y2;
		stak[++top]=(node){5,x,vis[x]};
		stak[++top]=(node){1,x,head[x]};
		stak[++top]=(node){2,x,tail[x]};
		stak[++top]=(node){3,pos[x],pre[pos[x]]};
		stak[++top]=(node){4,pos[x],suf[pos[x]]};
		stak[++top]=(node){6,pos[x],ans[pos[x]]};
		vis[x]=1,head[x]=tail[x]=x;
		y1=0;
		if(head[x-1]) ans[pos[x]]-=gx((x-1)-max(L[pos[x]],head[x-1])+1),y1+=(x-1)-max(L[pos[x]],head[x-1])+1;
		if(tail[x+1]) ans[pos[x]]-=gx(min(R[pos[x]],tail[x+1])-(x+1)+1),y1+=min(R[pos[x]],tail[x+1])-(x+1)+1;
		y1++;
		ans[pos[x]]+=gx(y1);
		if(x==L[pos[x]]||head[x-1]&&head[x-1]<=L[pos[x]]) pre[pos[x]]=max(x,min(R[pos[x]],tail[x+1]))-L[pos[x]]+1;
		if(x==R[pos[x]]||tail[x+1]&&tail[x+1]>=R[pos[x]]){
			suf[pos[x]]=R[pos[x]]-x+1;
			if(head[x-1]) suf[pos[x]]=R[pos[x]]-max(L[pos[x]],head[x-1])+1;
		}
		if(head[x-1]){
			int y1=head[x-1],y2=tail[x];
			stak[++top]=(node){1,x-1,head[x-1]};
			stak[++top]=(node){2,x-1,tail[x-1]};
			head[x-1]=tail[x-1]=0;
			head[x]=tail[x]=0;
			link(y1,y2);
		}
		if(tail[x+1]){
			int y1=head[x],y2=tail[x+1];
			stak[++top]=(node){1,x+1,head[x+1]};
			stak[++top]=(node){2,x+1,tail[x+1]};
			head[x]=tail[x]=0;
			head[x+1]=tail[x+1]=0;
			link(y1,y2);
		}
	}
	void w(){
		for(int i=1;i<=n;i++) printf("%d ",pos[i]);
		puts("");
		for(int i=1;i<=n;i++) printf("%d ",head[i]);
		puts("");
		for(int i=1;i<=n;i++) printf("%d ",tail[i]);
		puts("");
		for(int i=1;i<=n;i++) printf("%d ",vis[i]);
		puts("");
		for(int i=1;i<=pos[n];i++) printf("%d ",pre[i]);
		puts("");
		for(int i=1;i<=pos[n];i++) printf("%d ",suf[i]);
		puts("");
		for(int i=1;i<=pos[n];i++) printf("%d ",ans[i]);
		puts("");
		puts("");
	}
	ll query(int x,int y){
		ll res=0,len=0;
		if(pos[x]==pos[y]){
			for(int i=x;i<=y;i++)
				if(!vis[i]) res+=gx(len),len=0;
				else len++;
			res+=gx(len);
		}
		else{
			for(int i=x;i<=R[pos[x]];i++)
				if(!vis[i]) res+=gx(len),len=0;
				else len++;
			for(int i=pos[x]+1;i<pos[y];i++)
				if(pre[i]==R[i]-L[i]+1)
					len+=pre[i];
				else{
					res+=gx(len+pre[i]);
					res+=ans[i];
					res-=gx(pre[i]);
					res-=gx(suf[i]);
					len=suf[i];
				}
			for(int i=L[pos[y]];i<=y;i++)
				if(!vis[i]) res+=gx(len),len=0;
				else len++;
			res+=gx(len);
		}
		return res;
	}
	void test(){
		int op,x,y,z;
		while(1){
			scanf("%d",&op);
			if(op==1){
				scanf("%d",&x);
				change(x);
			}
			if(op==2){
				scanf("%d%d",&x,&y);
				printf("%lld\n",query(x,y));
			}
			if(op==3)
				rep(0);
			if(op==4)
				w();
		}
	}
}A;
struct ques{int l,r,v,id;}b[N];
bool cmp(ques x,ques y){return x.v<y.v;}
struct qwq{
	int K,pos[N],L[N],R[N],op[N],X[N],Y[N],Z[N],tot1;
	int vis[N],val[N];ll ans[N];
	void work(){
		K=sqrt(m);
		for(int i=1;i<=m;i++) pos[i]=(i-1)/K+1;
		for(int i=1;i<=m;i++) R[pos[i]]=i;
		for(int i=m;i;i--) L[pos[i]]=i;
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&op[i],&X[i],&Y[i]);
			if(op[i]==2) scanf("%d",&Z[i]);
		}
		A.Pre();
		for(int i=1,to;i<=pos[m];i++){
			tot1=0;
			for(int j=L[i];j<=R[i];j++)
				if(op[j]==1) vis[X[j]]=1;
				else b[++tot1]=(ques){X[j],Y[j],Z[j],j};
			sort(b+1,b+tot1+1,cmp);
			to=1;
			for(int j=1,las;j<=tot1;j++){
				while(to<=n&&c[to].v<=b[j].v){
					if(!vis[c[to].id]) A.change(c[to].id);
					to++;
				}
				las=A.top;
				for(int p=L[i];p<=R[i];p++) val[X[p]]=(a[X[p]]<=b[j].v);
				for(int p=L[i];p<=b[j].id;p++)
					if(op[p]==1)
						val[X[p]]=(Y[p]<=b[j].v);
				for(int p=L[i];p<=R[i];p++)
					if(op[p]==1&&val[X[p]])
						A.change(X[p]);
				ans[b[j].id]=A.query(b[j].l,b[j].r);
				A.rep(las);
			}
			A.rep(0);
			for(int j=L[i];j<=R[i];j++)
				if(op[j]==1) a[X[j]]=Y[j];
			l1=l2=0;
			for(int j=1;j<=n;j++)
				if(vis[c[j].id]) b1[++l1]=(U){c[j].id,a[c[j].id]};
				else b2[++l2]=c[j];
			sort(b1+1,b1+l1+1,cmp1);
			msort();
			for(int j=L[i];j<=R[i];j++)
				if(op[j]==1) vis[X[j]]=0;
		}
		for(int i=1;i<=m;i++)
			if(op[i]==2)
				printf("%lld\n",ans[i]);
	}
}B;
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),c[i].v=a[i],c[i].id=i;
	sort(c+1,c+n+1,cmp1);
//	A.Pre();
//	A.test();
	B.work();
	return 0;
}


/*
5 2
5 2 5 2 1 
1 3 1
2 3 4 5
*/