RT。前三个点 950ms，其他全 AC。

#include<bits/stdc++.h>
#define int long long
#define N 100000
#define B 500
#define NM 500 
using namespace std;
struct node{int id,num;};
bool cmp(node x,node y){return x.num<y.num;}
struct szsz{
	int n,a[N+5];
	inline void init(int x)
	{n=x;memset(a,0,sizeof(a));}
	inline void upd(int x,int y)
	{while(x<=n)a[x]+=y,x+=x&-x;}
	inline int query(int x)
	{int r=0;while(x>0)r+=a[x],x-=x&-x;return r;}
	inline int query(int x,int y)
	{return query(y)-query(x-1);}
};
szsz t;
int n,m,nm,la,a[N+5],L[NM+5],R[NM+5],I[N+5],pre[N+5],suf[N+5],app[NM+5][N+5],btb[NM+5][NM+5];
node srt[N+5];
inline int merge(int x,int y,int z,int t)
{
	int l=I[x],r=I[z],totj=0,res=0;
	for(int i=L[l],j=L[r]-1;i<=R[l];i++)
	{
		while(j<R[r]&&srt[j+1].num<srt[i].num)
		{
			j++;
			if(srt[j].id<=t&&srt[j].id>=z) totj++;
		}
		if(srt[i].id<=y&&srt[i].id>=x)
			res+=totj;
	}
	return res;
}
inline int read()
{
    int q=0;
    char ch=getchar();
    while(ch<48) ch=getchar();
    while(ch>47) q=(q<<1)+(q<<3)+(ch^48),ch=getchar();
    return q;
}
signed main()
{
	cin>>n>>m;nm=(n+B-1)/B;
	for(int i=1;i<=nm;i++) L[i]=i*B-B+1,R[i]=i*B;
	R[nm]=n;
	for(int i=1;i<=n;i++) I[i]=(i+B-1)/B,a[i]=read();
	for(int i=1;i<=nm;i++)
	{
		t.init(n);
		for(int j=L[i];j<=R[i];j++)
			pre[j]=(j==L[i]?0:pre[j-1])+j-L[i]-t.query(a[j]),
			t.upd(a[j],1);
		t.init(n);
		for(int j=R[i];j>=L[i];j--)
			suf[j]=suf[j+1]+t.query(a[j]),
			t.upd(a[j],1);
		for(int j=L[i];j<=R[i];j++)
			srt[j].id=j,srt[j].num=a[j];
		sort(srt+L[i],srt+R[i]+1,cmp);
	}
	for(int i=1;i<=nm;i++)
	{
		for(int j=1;j<=n;j++) app[i][j]=app[i-1][j];
		for(int j=L[i];j<=R[i];j++) app[i][a[j]]++;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=nm;j++)
			app[j][i]+=app[j][i-1];
	for(int i=1;i<=nm;i++)
		for(int j=i;j<=nm;j++)
		{
			btb[i][j]=btb[i][j-1]+pre[R[j]];
			for(int k=L[j];k<=R[j];k++)
				btb[i][j]+=R[j-1]-L[i]+1
				-app[j-1][a[k]]+app[i-1][a[k]];
		}
	while(m--)
	{
		int x,y;
		x=read(),y=read();
		x^=la,y^=la;
	//	if(x>y) exit(0);
		if(I[x]==I[y])
		{
			int res=pre[y]-(x==L[I[x]]?0:pre[x-1]);
			res-=merge(L[I[x]],x-1,x,y);
			printf("%lld\n",la=res);
		}
		else
		{
			int res=suf[x]+pre[y]+btb[I[x]+1][I[y]-1];
			for(int i=x;i<=R[I[x]];i++)
				res+=app[I[y]-1][a[i]]-app[I[x]][a[i]];
			for(int i=L[I[y]];i<=y;i++)
				res+=app[I[y]-1][n]-app[I[y]-1][a[i]]
					-app[I[x]][n]+app[I[x]][a[i]];
			res+=merge(x,R[I[x]],L[I[y]],y);
			printf("%lld\n",la=res);
		}
	}
	return 0;
}
/*9 100
1 9 2 6 3 8 5 7 4*/

提交记录