RT,悬赏两个关注！

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int B=500;
const int N=100000+10;
const int BLO=N/B+5;
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline long long Read(){
	long long x=0;int f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,m,a[N],b[N],blo,lft[BLO],rht[BLO],bel[N],tr[N],L[N],R[N],iv[N];
long long ans[BLO][BLO],las,g[N][BLO];int now[N];
inline int query(int x){int res=0;for(;x;x-=x&(-x))res+=tr[x];return res;}
inline void add(int x){for(;x<=n;x+=x&(-x))++tr[x];}
inline void clear(int x){for(;x<=n;x+=x&(-x))tr[x]=0;}
inline int merge(int b1,int b2,int l,int r){
	int p1=lft[b1],p2=lft[b2],e1=rht[b1],e2=rht[b2],cnt=0,res=0;
	while(p1<=e1){
		if(p2>e2||b[p2]>b[p1]){
			if(iv[b[p1]]>=l)res+=cnt;
			++p1;//continue;
		}else{
			if(iv[b[p2]]<=r)++cnt;
			++p2;//continue;
		}
	}return res;
}
inline long long Query(int l,int r){
	if(bel[l]==bel[r]){
		if(l==lft[bel[l]])return L[r];
		int bi=bel[l],res=L[r]-L[l-1];
		int p1=lft[bi],p2=p1,e=rht[bi],cnt=0;
		while(p1<=e){
			if(p2>e||b[p2]>b[p1]){
				if(iv[b[p1]]<l)res-=cnt;
				++p1;//continue;
			}else{
				if(iv[b[p2]]<=r&&iv[b[p2]]>=l)++cnt;
				++p2;//continue;
			}
		}return res;
	}
	long long res=R[l]+L[r]+merge(bel[l],bel[r],l,r);
	int br=bel[r]-1,bl=bel[l],len=rht[br]-rht[bl];
	res+=ans[bel[l]+1][bel[r]-1]+1ll*(r-rht[br])*len;
	//for(int i=l;i<=rht[bel[l]];++i)res+=g[i][br]-g[i][bl];
	res+=g[rht[bl]][br]-g[l-1][br]-g[rht[bl]][bl]+g[l-1][bl];
	//for(int i=lft[bel[r]];i<=r;++i)res-=g[i][br]-g[i][bl];
	res-=g[r][br]-g[rht[br]][br]-g[r][bl]+g[rht[br]][bl];
	return res;
}
int main(){
//	freopen("P5046.in","r",stdin);
//	freopen("P5046.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]=b[i]=read();
	for(int i=1;i<=n;++i)iv[a[i]]=i;
	for(;;){
		++blo;lft[blo]=rht[blo-1]+1;
		rht[blo]=min(lft[blo]+B-1,n);
		int l=lft[blo],r=rht[blo];
		for(int j=l;j<=r;++j)bel[j]=blo;
		sort(b+l,b+r+1);
		for(int j=l;j<=r;++j)
			ans[blo][blo]+=query(n-a[j]+1),add(n-a[j]+1),L[j]=ans[blo][blo];
		for(int j=l;j<=r;++j)clear(n-a[j]+1);
		for(int j=r;j>=l;--j)R[j]+=R[j+1]+query(a[j]),add(a[j]);
		for(int j=l;j<=r;++j)clear(a[j]);
		for(int j=1,k=l,cur=0;j<=n;++j){
			if(k<=r&&j>=b[k])++cur,++k;int id=iv[j];
			g[id][blo]=g[id][blo-1]+cur;
			if(id<l)ans[bel[id]][blo]+=cur;
		}if(r==n)break;
	}
	for(int i=1;i<=blo;++i){
		int sum=ans[i][i];
		for(int j=i-1;j>=1;--j)
			sum+=ans[j][i],ans[j][i]=ans[j][i-1]+sum;
		for(int j=1;j<=n;j++)g[j][i]+=g[j-1][i];
	}//return 0;
	for(int i=1;i<=m;i++){
		long long l,r;
		scanf("%lld%lld",&l,&r);
		l^=las,r^=las;
		if(l>r)swap(l,r);
		assert(l>=1);assert(r<=n);
		printf("%lld\n",las=Query(l,r));
	}
	return 0;
}

目前能过后两个点，分别是 612ms,563ms，交了 4 页了，救救孩子吧！