RT，评测记录全 T 了，已经加了我能想象到的所有优化了。。。。

记录

#include<bits/stdc++.h>
#define ll long long
#define doub long double
#define endl "\n"
#define push_back emplace_back
using namespace std;
const int maxn=1e5+7;
const int maxB=507;
int n,m;
int a[maxn];
int tmp[maxn];

//离散化

void DC(){
	for(int i=1;i<=n;i++)tmp[i]=a[i];
	sort(tmp+1,tmp+n+1);
	int u=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(tmp+1,tmp+u+1,a[i])-tmp;
}

//莫队常规 

int bel[maxn];
int B;
int Bc;
int L[maxB];
int R[maxB];
struct qry{
	int l,r,id;
}qq[maxn];
ll qa[maxn];
bool cmp(qry x,qry y){
	return bel[x.l]==bel[y.l]?x.r<y.r:bel[x.l]<bel[y.l];
}
int l=1,r=0;

//二离特色

struct RG{
	int l,r,id,s;
}; 
vector<RG> Vp[maxn],Vs[maxn];

//值域数据结构（预处理 g(x,x-1) 与 g(x,x),扫描线分块）。
//莫队的分块边界与这里的值域分块是共用的。 

int g1[maxn];
int g2[maxn];
ll sg1[maxn];
ll sg2[maxn];

//这里只开两个数组的原因是因为g(1或2)(x,x-1)=g(1或2)(x,x). 
//g1:大 g2:小g1[i]=g1d[i]=qpre(a[i]-1); 

inline int lb(int x){return x&(-x);}
int T[maxn];
void add(int x,int dt){
	while(x<=n){
		T[x]+=dt;
		x+=lb(x);
	}
}
int g(int x){
	int ans=0;
	while(x){
		ans+=T[x];
		x-=lb(x);
	}
	return ans;
}
struct SqrtB{
	int t[maxn];
	int S[maxB];
	int PRE[maxB],SUF[maxB];
	int pr[maxn],sf[maxn];
	inline void init(){
		memset(t,0,sizeof(t));
		memset(S,0,sizeof(S));
		memset(PRE,0,sizeof(PRE));
		memset(SUF,0,sizeof(SUF));
		memset(pr,0,sizeof(pr));
		memset(sf,0,sizeof(sf));
	}
	inline void Hr(int id){
		pr[L[id]]=t[L[id]];
		for(int i=L[id]+1;i<=R[id];i++)pr[i]=pr[i-1]+t[i]; 
		sf[R[id]]=t[R[id]];
		for(int i=R[id]-1;i>=L[id];i--)sf[i]=sf[i+1]+t[i];
		S[id]=pr[R[id]];
		for(int i=1;i<=Bc;i++)PRE[i]=PRE[i-1]+S[i];
		for(int i=Bc;i>=1;i--)SUF[i]=SUF[i+1]+S[i];
	}
	inline void upd(int x,int dt){
		t[x]+=dt;
		Hr(bel[x]);
	}
	inline int qpre(int x){return pr[x]+PRE[bel[x]-1];}
	inline int qsuf(int x){return sf[x]+SUF[bel[x]+1];}
}BK;

//fastIO

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
} 
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){
		putchar(x+'0');
		return;
	}
	write(x/10),putchar(x%10+'0');
}
signed main(){
	freopen("P5047_1.in","r",stdin);
	freopen("In.out","w",stdout);
	n=read(),m=read();
	B=335;
	memset(L,0x3f,sizeof(L));
	for(int i=1;i<=n;i++){
		a[i]=read();
		bel[i]=(i-1)/B+1;
		L[bel[i]]=min(i,L[bel[i]]);
		R[bel[i]]=max(i,R[bel[i]]);
	}
	bel[n+1]=n/B+1;
	Bc=bel[n+1];
	BK.init();
	DC();
	for(int i=1;i<=n;i++){
		add(a[i],1);
		g1[i]=i-g(a[i]),g2[i]=g(a[i]-1);
		sg1[i]=sg1[i-1]+g1[i],sg2[i]=sg2[i-1]+g2[i];
//		cout<<g1[i]<<" "<<g2[i]<<endl;
	}
//	for(int i=1;i<=n;i++)cout<<g1[i]<<" ";
//	cout<<endl;
//	for(int i=1;i<=n;i++)cout<<g2[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=m;i++){
		qq[i].l=read(),qq[i].r=read();
		qq[i].id=i;
	}
	sort(qq+1,qq+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(r<qq[i].r){
			qa[qq[i].id]+=sg1[qq[i].r]-sg1[r];
			Vs[l-1].push_back((RG){r+1,qq[i].r,qq[i].id,-1});
			r=qq[i].r;
		}
//		cout<<l<<" "<<r<<" "<<qq[i].l<<" "<<qq[i].r<<endl;
//		cout<<qa[qq[i].id]<<endl;
		if(l>qq[i].l){
			qa[qq[i].id]-=sg2[l-1]-sg2[qq[i].l-1];
			Vp[r].push_back((RG){qq[i].l,l-1,qq[i].id,1});
			l=qq[i].l;
		}
//		cout<<l<<" "<<r<<" "<<qq[i].l<<" "<<qq[i].r<<endl;
//		cout<<qa[qq[i].id]<<endl;
		if(r>qq[i].r){
			qa[qq[i].id]-=sg1[r]-sg1[qq[i].r];
			Vs[l-1].push_back((RG){qq[i].r+1,r,qq[i].id,1});
			r=qq[i].r;
		}
//		cout<<l<<" "<<r<<" "<<qq[i].l<<" "<<qq[i].r<<endl;
//		cout<<qa[qq[i].id]<<endl;
		if(l<qq[i].l){
			qa[qq[i].id]+=sg2[qq[i].l-1]-sg2[l-1];
			Vp[r].push_back((RG){l,qq[i].l-1,qq[i].id,-1});
			l=qq[i].l;
		}
//		cout<<l<<" "<<r<<" "<<qq[i].l<<" "<<qq[i].r<<endl;
//		cout<<qa[qq[i].id]<<endl;
	}
//	cout<<qa[1]<<endl;
	for(int i=0;i<=n;i++){
		if(i)BK.upd(a[i],1);
		for(RG p:Vp[i]){
			for(int j=p.l;j<=p.r;j++){
				qa[p.id]+=BK.qpre(a[j]-1)*p.s;
			}
		}
		for(RG p:Vs[i]){
			for(int j=p.l;j<=p.r;j++){
				qa[p.id]+=BK.qsuf(a[j]+1)*p.s;
			}
		}
	}
	for(int i=1;i<=m;i++)qa[qq[i].id]+=qa[qq[i-1].id];
	for(int i=1;i<=m;i++)write(qa[i]),putchar('\n');
	cout.flush();
	return 0;
}