下列代码在此题中 TLE on test4。

将此代码第 30 行前加入 top=n 即可通过此题。

求问为什么。

#include<bits/stdc++.h>
#define rpt(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
typedef long long LL;
const int N=5e5+10,M=5e5+10,K=5e5+10;
int n,m,a[N],s[N],top;
LL sum[N],f[N];
struct que{int l,r,xb; LL ans;}q[N];
vector<array<int,4> > v[N];
int tp,B,cnt,bl[N],L[M],R[M];
LL tag[M][2],num[K][2];
bool cmp(que a,que b){
	if(bl[a.l]!=bl[b.l])return a.l<b.l;
	return bl[a.l]&1?a.r<b.r:a.r>b.r;
}
void mdf(int x){
	rpt(i,x,R[bl[x]])num[i][0]++,num[i][1]+=s[x];
	rpt(i,bl[x],cnt)tag[i][0]++,tag[i][1]+=s[x];
}
LL qry(int x,int k){
	if(bl[x]>cnt||bl[x]<1)return 0;
	return tag[bl[x]-1][k]+num[x][k];
}
LL ans[N],now;
int main(){
	scanf("%d%d",&n,&m);
	rpt(i,1,n)scanf("%d",&a[i]),s[i]=a[i];
	sort(s+1,s+n+1),top=unique(s+1,s+n+1)-s-1;
	rpt(i,1,n)a[i]=lower_bound(s+1,s+top+1,a[i])-s;
	B=sqrt(top);
	rpt(i,1,top)bl[i]=(i-1)/B+1; cnt=bl[top];
	rpt(i,1,cnt)L[i]=(i-1)*B+1,R[i]=i*B; R[cnt]=top;
	rpt(i,1,n)sum[i]=sum[i-1]+s[a[i]];
	rpt(i,1,n)mdf(a[i]),f[i]=qry(a[i]-1,0)*s[a[i]]+qry(top,1)-qry(a[i],1);
	rpt(i,1,top)num[i][0]=num[i][1]=0;
	rpt(i,1,cnt)tag[i][0]=tag[i][1]=0;
	rpt(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].xb=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	rpt(i,2,n)f[i]+=f[i-1];
	rpt(i,1,m){
		int L=q[i].l,R=q[i].r;
		if(r<R)v[l-1].push_back({r+1,R,-1,i}),q[i].ans+=(f[R]-f[r]),r=R;
		if(l>L)v[r].push_back({L,l-1,1,i}),q[i].ans-=(f[l-1]-f[L-1]),l=L;
		if(r>R)v[l-1].push_back({R+1,r,1,i}),q[i].ans-=(f[r]-f[R]),r=R;
		if(l<L)v[r].push_back({l,L-1,-1,i}),q[i].ans+=(f[L-1]-f[l-1]),l=L;
	}
	rpt(i,1,n){
		mdf(a[i]);
		for(auto u:v[i])rpt(k,u[0],u[1])
			q[u[3]].ans+=u[2]*(qry(a[k]-1,0)*s[a[k]]+qry(top,1)-qry(a[k],1));
	}
	rpt(i,2,m)q[i].ans+=q[i-1].ans;
	rpt(i,1,m)ans[q[i].xb]=q[i].ans+sum[q[i].r]-sum[q[i].l-1];
	rpt(i,1,m)printf("%lld\n",ans[i]);
	return 0;
}