提交记录

只有 76pts，要崩溃惹

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
typedef long long ll;
const ll N=1e5+5,KL=700;
int n,m,a[N];
int K,pos[N],L[KL],R[KL],cnt[KL][N];
int pre[N],suf[N];
ll f[KL][KL];
struct node{int id,v;}b[N];
bool cmp(node x,node y){return x.v<y.v;}
int ask(int l1,int r1,int l2,int r2){
	if(l1>r1||l2>r2) return 0;
	int k1=pos[l1],k2=pos[l2];
	int t1=L[k1],t2=L[k2],c=0,res=0;
	while(t1<=R[k1]&&!(l1<=b[t1].id&&b[t1].id<=r1)) t1++;
	while(t2<=R[k2]&&!(l2<=b[t2].id&&b[t2].id<=r2)) t2++;
	for(;t1<=R[k1]||t2<=R[k2];){
		if(t1<=R[k1]&&(t2>R[k2]||b[t1].v<b[t2].v)) t1++,c++;
		else t2++,res+=c;
		while(t1<=R[k1]&&!(l1<=b[t1].id&&b[t1].id<=r1)) t1++;
		while(t2<=R[k2]&&!(l2<=b[t2].id&&b[t2].id<=r2)) t2++;
	}
	return res;
}
struct BIT{
	int c[N];
	void add(int x,int y){for(;x<=n;x+=(x&(-x))) c[x]+=y;}
	int query(int x){
		int res=0;
		for(;x;x-=(x&(-x))) res+=c[x];
		return res;
	}
	void cl(int x){for(;x<=n;x+=(x&(-x))) c[x]=0;}
}A;
char *p1,*p2,buf[10000005];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
ll read(){
    ll x=0,f=1;char ch=nc();
    while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
    while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();
   	return x*f;
}
int main(){
	n=read();m=read();K=min((int)sqrt(n),400);
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) a[i]=n-a[i]+1;
	for(int i=1;i<=n;i++) b[i].v=a[i],b[i].id=i;
	for(int i=1;i<=n;i++) pos[i]=(i-1)/K+1;
	for(int i=1;i<=n;i++) R[pos[i]]=i;
	for(int i=n;i;i--) L[pos[i]]=i;
	for(int i=1;i<=pos[n];i++){
		for(int j=L[i];j<=R[i];j++) cnt[i][a[j]]++;
		for(int j=1;j<=n;j++) cnt[i][j]+=cnt[i][j-1];
		for(int j=1;j<=n;j++) cnt[i][j]+=cnt[i-1][j];
		for(int j=L[i];j<=R[i];j++){
			pre[j]=((j==L[i])?0:pre[j-1])+A.query(a[j]);
			A.add(a[j],1);
		}
		for(int j=L[i];j<=R[i];j++) A.cl(a[j]);
		for(int j=R[i];j>=L[i];j--){
			suf[j]=((j==R[i])?0:suf[j+1])+A.query(n)-A.query(a[j]);
			A.add(a[j],1);
		}
		for(int j=L[i];j<=R[i];j++) A.cl(a[j]);
		sort(b+L[i],b+R[i]+1,cmp);
		f[i][i]=pre[R[i]];
	}
	for(int l=2;l<=pos[n];l++)
		for(int i=1,j;i<=pos[n];i++){
			j=i+l-1;
			f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+ask(L[i],R[i],L[j],R[j]);
		}
	ll x,y,las=0;
	while(m--){
		x=read();y=read();
		x^=las,y^=las;
		if(x>n||y>n||x>y) return 0;
		if(pos[x]==pos[y]){
			las=pre[y]-((L[pos[x]]==x)?0:pre[x-1]);
			las-=ask(L[pos[x]],x-1,x,y);
			printf("%lld\n",las);
		}
		else{
			las=suf[x]+f[pos[x]+1][pos[y]-1]+pre[y]+ask(x,R[pos[x]],L[pos[y]],y);
			for(int i=x;i<=R[pos[x]];i++) las+=(cnt[pos[y]-1][n]-cnt[pos[y]-1][a[i]])-(cnt[pos[x]][n]-cnt[pos[x]][a[i]]);
			for(int i=L[pos[y]];i<=y;i++) las+=cnt[pos[y]-1][a[i]]-cnt[pos[x]][a[i]];
			printf("%lld\n",las);
		}
	}
	return 0;
}