我本地生成了询问全是 $1$ 到 $n$ 的数据，然后不到0.5s，但是前三个点还是严重超时。

然后我想不出什么数据比全满的询问还强了（

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int B=280;
const int mx=B+5;
const int mc=N/B+5;
typedef long long ll;
int n,m,T,a[N],idx[N];
int mp[N],L[mc],R[mc];
int rk[mc][mx],pos[N];
int p[N][mx];
int pre[mc][N];
ll c[mc][mc];
ll c1[mc][mc];
ll c2[N];
int sum[mc];
int qry1(int l,int r){
	int z=mp[l],ans=0;
	for(int i=l;i<=r;++i){
		ans+=p[i][pos[i]];
		if(l!=L[z])ans-=p[l-1][pos[i]];
	}
	return ans;
}//散块内部
int aa[N],bb[N];
ll qry(int l,int r){
	int _l=R[mp[l]],_r=L[mp[r]];
	ll ans=qry1(l,_l)+qry1(_r,r);
	int bg=mp[_l+1],ed=mp[_r-1];
	if(bg<=ed){
		ans+=sum[ed]-sum[bg-1];
		for(int i=_r;i<=r;++i){
			ans+=pre[ed][a[i]],
			ans-=pre[bg-1][a[i]];
		}
		for(int i=l;i<=_l;++i){
			ans+=pre[ed][n],
			ans-=pre[bg-1][n],
			ans-=pre[ed][a[i]-1],
			ans+=pre[bg-1][a[i]-1];
		}
		ans+=c2[ed]-c2[bg-1];
		ans-=c1[bg-1][ed]-c1[bg-1][bg-1];
	}
	int sz1=0,sz2=0;
	for(int i=L[mp[l]];i<=R[mp[l]];++i)
		if(idx[i]>=l)
			aa[sz1++]=idx[i];
	for(int i=L[mp[r]];i<=R[mp[r]];++i)
		if(idx[i]<=r)
			bb[sz2++]=idx[i];
	int t1=0,t2=0,cnt=0;
	for(int i=1;i<=_l-l+1+r-_r+1;++i){
		if(t2==sz2||(t1<sz1&&a[aa[t1]]<a[bb[t2]]))
			cnt++,t1++;
		else ans+=cnt,t2++;
	}
	return ans;
}
#define gc()(xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<20,stdin),xS==xTT)?0:*xS++)
#define pc(x)(p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
char xch,xB[1<<20],*xS=xB,*xTT=xB,obuf[1000000],*p3=obuf;
inline int read(){char ch=gc();int x=0,f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}return x*f;}
int main(){
//	freopen("xx.in","r",stdin);
//	freopen("qwq.out","w",stdout);
	cin>>n>>m;
	T=(n-1)/B+1;
	for(int i=1;i<=n;++i)
		a[i]=read(),a[i]=n-a[i]+1,idx[i]=i;
	for(int i=1;i<=n;++i)
		mp[i]=(i-1)/B+1;
	for(int i=1;i<=T;++i){
		L[i]=(i-1)*B+1;
		R[i]=min(i*B,n);
		sort(idx+L[i],idx+R[i]+1,[](int x,int y){return a[x]<a[y];});
		for(int j=L[i];j<=R[i];++j)
			rk[i][j-L[i]+1]=a[idx[j]],pos[idx[j]]=j-L[i];
		for(int j=L[i];j<=R[i];++j)for(int k=1;k<=R[i]-L[i]+1;++k)
   			p[j][k]=(j==L[i]?0:p[j-1][k])+(a[j]<=rk[i][k]);
		for(int j=1,k=0;j<=n;++j){
			while(k+1<=R[i]-L[i]+1&&rk[i][k+1]<=j)k++;
			pre[i][j]=pre[i-1][j]+k;
		}
		for(int j=1;j<i;++j)for(int k=1;k<=R[i]-L[i]+1;++k)
			c[j][i]=c[j][i]+pre[j][rk[i][k]];
		for(int j=L[i];j<=R[i];++j)for(int k=j+1;k<=R[i];++k)
			sum[i]+=a[j]<a[k];
		sum[i]+=sum[i-1];
	}
	for(int i=2;i<=T;++i)
		c2[i]=c2[i-1]+c[i-1][i];
	for(int i=1;i<=T;++i)
		for(int j=1;j<=T;++j)
			c1[i][j]=c1[i][j-1]+c[i][j];
//	cerr<<clock()<<endl;
	int l,r;ll lst=0;
	while(m--){
		l=read(),r=read();
		l^=lst,r^=lst;
		if(mp[l]==mp[r])printf("%lld\n",lst=qry1(l,r));
		else printf("%lld\n",lst=qry(l,r));
	}
}

求给一组能卡掉我的数据（