我认为我已经做到极致了，但仍然卡不过去呀啊啊啊啊！

评测记录：https://www.luogu.com.cn/record/50085812

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#define M 670
#define N 100003
using namespace std;
int f[M][210][210],sum[M][N],a[N],p[N],l[N],r[N],id[N],b[N],s,len;
int n,T,B,C,ss[M],k,l1[N],l2[N];
long long g[M][M],ans,x,y;
bool cmp(int x,int y)
{
	return a[x]<a[y];
}
char c;
inline void fread(int&a)
{
	a=0;
	while(c>'9'||c<'0') c=getchar();
	while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
}
void work(int k)
{
	register int i,j;
	sort(p+l[k],p+r[k]+1,cmp);
	len=0;
	for(i=l[k];i<=r[k];i++) b[++len]=a[i];
	for(i=1;i<=len;i++)
	{
		s=0;
		for(j=i-1;j;j--)
		{
			if(b[i]<b[j]) s++;
			f[k][j][i]+=s;
		}
	}
	for(i=1;i<len;i++)
	{
		for(j=i+1;j<=len;j++)
			f[k][i][j]+=f[k][i][j-1];
	}
	for(i=1;i<=len;i++) sum[k][b[i]]++;
	for(i=1;i<=n;i++) sum[k][i]+=sum[k][i-1];
	for(i=1;i<=n;i++) sum[k][i]+=sum[k-1][i];
	ss[k]=ss[k-1]+f[k][1][r[k]-l[k]+1];
}
inline int merge(int*a,int*b)
{
	register int ans=0;
	for(register int i=1,j=1;i<=a[0];i++)
	{
		while(j<=b[0]&&b[j]<a[i]) j++;
		ans+=j-1;
	}
	return ans;
}
int main()
{
	fread(n);
	fread(T);
	B=150;
	register int i,j,k1,k2;
	for(i=1;i<=n;i++)
	{
		fread(a[i]);
		id[i]=i/B+1;
		p[i]=i;
		if(id[i]!=id[i-1]) r[i/B]=i-1,l[i/B+1]=i;
	}
	C=id[n];
	r[C]=n;
	for(i=1;i<=C;i++)
		work(i);
	for(i=1;i<=C;i++)
	{
		for(j=i-1;j;j--)
		{
			for(k=l[j];k<=r[j];k++)
			{
				ans+=(sum[i][a[k]]-sum[i-1][a[k]]);
			}
			g[j][i]=ans;
		}
		ans=0;
	}
	for(i=1;i<C;i++)
		for(j=i+2;j<=C;j++)
			g[i][j]+=g[i][j-1];
	for(i=1;i<=C;i++)
		for(j=i;j<=C;j++)
			g[i][j]+=ss[j]-ss[i-1];
	while(T--)
	{
		scanf("%lld%lld",&x,&y);
		x^=ans,y^=ans;
		if(x<0||y<0||x>n||y>n||x>y) {printf("-1");return 0;}
		k1=id[x],k2=id[y];
		if(k1==k2)
		{
			ans=f[k1][x-l[k1]+1][y-l[k1]+1];
			printf("%lld\n",ans);
			continue;
		}
		l1[0]=l2[0]=0;
		for(i=l[k1];i<=r[k1];i++)
			if(p[i]>=x) l1[++l1[0]]=a[p[i]];
		for(int i=l[k2];i<=r[k2];i++)
			if(p[i]<=y) l2[++l2[0]]=a[p[i]];
		ans=merge(l1,l2);
		for(i=x;i<=r[k1];i++)
		{
			ans+=(sum[k2-1][a[i]]-sum[k1][a[i]]);
		}
		for(i=l[k2];i<=y;i++)
		{
			ans+=r[k2-1]-l[k1+1]+1-(sum[k2-1][a[i]]-sum[k1][a[i]]);
		}
		ans+=g[k1+1][k2-1]+f[k1][x-l[k1]+1][r[k1]-l[k1]+1]+f[k2][1][y-l[k2]+1];
		printf("%lld\n",ans);
	}
	return 0;
}

求大佬指点一二