题

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define N 100005
#define S 805
#define ll long long
#define rd read()
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
static char buf[100000], * pa(buf), * pb(buf);
inline unsigned int read()
{
	register unsigned int x=0,s=gc;
	while(s<'0'||s>'9')s=gc;
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
struct ostream{
	char buf[9000005],*s;
	inline ostream(){s=buf;}
	inline void operator<<(long long d){
		if(!d){
			*s++='0';
		}else{
			static long long w;
			for(w=1;w<=d;w*=10);
			for(;w/=10;d%=w)*s++=d/w^'0';
		}
		*s++='\n';
	}
	inline ostream&operator<<(const char&c){*s++=c;return*this;}
	inline~ostream(){fwrite(buf,1,s-buf,stdout);}
}cout;
struct pd
{
	int v,ps;
	inline bool operator <(const pd &o)const{return v<o.v;}
}p[N];
int n,q,a[N],block,tot,bl[N],L[S],R[S];
ll pre[N],nxt[N],last;
ll cnt[S][N],ans[S][S],c[N];
inline void add(register int x,const register int y){while(x<=n)c[x]+=y,x+=(x&-x);}
inline ll ak(register int x){register ll sum=0;while(x)sum+=c[x],x^=(x&-x);return sum;}
inline void init()
{
	ll sum=0;
	for(register int x(1);x<=tot;sum=0,++x)
	{
		L[x]=R[x-1]+1,R[x]=min(x*block,n);
		add(a[L[x]],1),cnt[x][a[L[x]]]=1;
		for(register int i=L[x]+1;i<=R[x];cnt[x][a[i]]=1,add(a[i++],1))pre[i]=pre[i-1]+(i-L[x])-ak(a[i]);
		for(register int i=L[x];i<=R[x];add(a[i++],-1));add(a[R[x]],1);
		for(register int i=R[x]-1;i>=L[x];add(a[i--],1))nxt[i]=nxt[i+1]+ak(a[i]);
		for(register int i=L[x];i<=R[x];add(a[i++],-1));
		for(register int i(1);i<=n;cnt[x][i]=sum+cnt[x-1][i],++i)sum+=cnt[x][i];
		ans[x][x]=pre[R[x]],std::sort(p+L[x],p+R[x]+1);
	}
}
inline ll calc(int l,int r,int l1,int r1,int l2,int r2)
{
	register int pos=L[r]-1;
	register ll sum=0,res=0;
	for(register int i=L[l];i<=R[l];++i)
		if(p[i].ps>=l1&&p[i].ps<=r1)
		{
			while(pos<=R[r]&&p[i].v>p[pos+1].v)
			{
				++pos;
				if(l2<=p[pos].ps&&p[pos].ps<=r2)++sum;
			}
			res+=sum;
		}
	return res;
}
int l,r;
inline void ask()
{
	const int b1=bl[l],b2=bl[r]; 
	if(b1==b2)
	{
		if(l==L[b1])last=pre[r];
		else last=pre[r]-pre[l-1]-calc(b1,b2,1,l-1,l,r);
		cout<<last;return;
	}
	ll res=nxt[l]+pre[r]+ans[b1+1][b2-1]+calc(b1,b2,l,R[b1],L[b2],r);
	for(register int i=l;bl[i]==b1;++i)res+=cnt[b2-1][a[i]]-cnt[b1][a[i]];
	for(register int i=L[b2];i<=r;++i)res+=cnt[b1][a[i]]-cnt[b2-1][a[i]];
	last=res+(r-L[b2]+1)*(R[b2-1]-L[b1+1]+1);
	cout<<last;
}
signed main()
{
	n=rd,q=rd,block=sqrt(n)/2+1,tot=n/block+(n%block?1:0);
	for(register int i(1);i<=n;bl[i]=(i-1)/block+1,p[i]={a[i]=rd,i},i++);
	init();
	for(register int i=2;i<=tot;++i)for(l=1,r=i;r<=tot;++l,++r)ans[l][r]=ans[l+1][r]+ans[l][r-1]-ans[l+1][r-1]+calc(l,r,L[l],R[l],L[r],R[r]);
	while(q--)l=rd^last,r=rd^last,ask();
	return 0;
}
/*
10 4
1 10 2 4 5 3 7 8 9 6
1 9
1 3
3 8
15 5
*/

前三个点过不去啊啊啊，T了大概90ms