RT，后面两个点和有些AC代码已经比较接近了，前面三个点还是 950ms+ /dk

#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=100010, B=369;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
	return s*w;
}
int n,m,a[N],blk,bl[N],tl[N],tr[N]; long long lsta,cnt[B][N];
int len[B],g[B][N],rk[N],pre[N],nxt[N];
struct Node { int w,id; }w[B][B];
inline bool cp(Node x,Node y) { return x.w<y.w; }
int u[N],v[N];
struct BIT
{
	int c[N];
	inline int lowbit(int x) { return x&(-x); }
	inline void Add(int x,int p)
	{
		for(;x<=n;x+=lowbit(x)) c[x]+=p;
	}
	inline int Ask(int x)
	{
		int tt=0;
		for(;x;x-=lowbit(x)) tt+=c[x];
		return tt;
	}
}A;
signed main()
{
	n=read(), m=read();
	blk=300;
	for(ri int i=1;i<=n;i++)
	{
		a[i]=read();
		bl[i]=(i-1)/blk+1;
		w[bl[i]][++len[bl[i]]]=(Node){a[i],i};
		g[bl[i]][a[i]]++;
	}
	for(ri int i=1;i<=bl[n];i++)
	{
		sort(w[i]+1,w[i]+1+len[i],cp);
		tl[i]=(i-1)*blk+1, tr[i]=min(i*blk,n);
		for(ri int j=1;j<=n;j++) g[i][j]+=g[i][j-1];
		for(ri int j=1;j<=len[i];j++) rk[w[i][j].w]=j;
		for(ri int j=tl[i];j<=tr[i];j++)
		{
			int bk=A.Ask(a[j]);
			pre[j]=j-tl[i]-bk, nxt[j]=rk[a[j]]-bk-1;
			A.Add(a[j],1);
		}
		for(ri int j=tl[i];j<=tr[i];j++) A.Add(a[j],-1);
	}
	for(ri int i=1;i<=n;i++)
	for(ri int j=1;j<=bl[n];j++)
	g[j][i]+=g[j-1][i];
	for(ri int i=1;i<=bl[n];i++)
	for(ri int j=i;j<=bl[n];j++)
	{
		cnt[i][j]=cnt[i][j-1];
		for(ri int k=tl[j];k<=tr[j];k++) cnt[i][j]+=(j-i)*blk-(g[j-1][a[k]]-g[i-1][a[k]])+nxt[k];
	}
	for(ri int i=1;i<=m;i++)
	{
		long long pl,pr;
		scanf("%lld%lld",&pl,&pr);
		int l,r;
		l=pl^lsta, r=pr^lsta;
		if(l>r) swap(l,r);
		int L=bl[l], R=bl[r];
		lsta=0;
		if(L==R)
		{
			for(ri int j=l;j<=r;j++) lsta+=nxt[j];
			if(r==tr[L]) { printf("%lld\n",lsta); continue; }
			for(ri int j=1;j<=len[L];j++)
			{
				if(w[L][j].id>=l && w[L][j].id<=r) u[++u[0]]=w[L][j].w;
				if(w[L][j].id>=r+1) v[++v[0]]=w[L][j].w;
			}
			int now=1;
			for(ri int j=1;j<=u[0];j++)
			{
				while(now<=v[0]&&v[now]<u[j]) now++;
				lsta-=now-1;
			}
			u[0]=v[0]=0;
			printf("%lld\n",lsta);
			continue;
		}
		lsta=cnt[L+1][R-1];
		for(ri int j=l;j<=tr[L];j++)
		{
			lsta+=g[R-1][a[j]]-g[L][a[j]]+nxt[j];
		}
		for(ri int j=tl[R];j<=r;j++)
		{
			lsta+=(R-L-1)*blk-(g[R-1][a[j]]-g[L][a[j]])+pre[j];
		}
		for(ri int j=1;j<=len[L];j++) if(w[L][j].id>=l) u[++u[0]]=w[L][j].w;
		for(ri int j=1;j<=len[R];j++) if(w[R][j].id<=r) v[++v[0]]=w[R][j].w;
		int now=1;
		for(ri int j=1;j<=u[0];j++)
		{
			while(now<=v[0]&&v[now]<u[j]) now++;
			lsta+=now-1;
		}
		u[0]=v[0]=0;
		printf("%lld\n",lsta);
	}
	return 0;
}