76分求卡常

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
namespace MYINPUT{
    const int S=(1<<20)+5;char B[S],*H=B,*T=B;
    inline char gc(){if(H==T) T=(H=B)+fread(B,1,S,stdin);return H==T?EOF:*H++;}
    inline ll fr(){ll x=0;bool fh=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-') fh=1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}return fh?-x:x;}
}using MYINPUT::fr;

int n,m,sum[638][100005],lk[638],rk[638],idk[100005],num[638],g[100005][162],kuainum[638][162][162]; 
long long p[638][638],last;
struct node{
	int id,x;
}a[100005],b[100005];
bool cmp(node s1,node s2){
	return s1.x<s2.x;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	n=fr(),m=fr();
	for(int i=1;i<=n;i++){
		a[i].x=fr();
		a[i].id=i;
		b[i]=a[i];
	}
	int len=sqrt(n)/2,kuai=(n+len-1)/len;
//	if(kuai*kuai!=n) kuai++,len++;
	for(int i=1;i<=kuai;i++){
		lk[i]=rk[i-1]+1,rk[i]=min(n,lk[i]+len-1);
		sort(b+lk[i],b+rk[i]+1,cmp);
		for(int j=lk[i];j<=rk[i];j++){
			idk[j]=i;
			sum[i][a[j].x]++;
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i-1][j];
		}
		for(int j=lk[i];j<=rk[i];j++){
			int cnt=0;
			for(int k=lk[i];k<j;k++){
				if(a[k].x>a[j].x) num[i]++,cnt++;
                if(a[k].x>a[j].x){
                    g[j][k-lk[i]+1]=g[j][k-lk[i]]+1;
                }else{
                    g[j][k-lk[i]+1]=g[j][k-lk[i]];
                }              
			}
		}
		for(int j=lk[i];j<=rk[i];j++){
			for(int k=j+1;k<=rk[i];k++){
				kuainum[i][j-lk[i]+1][k-lk[i]+1]=kuainum[i][j-lk[i]+1][k-lk[i]]+g[k][k-lk[i]]-g[k][j-lk[i]]; 
			}
		}
	}
	for(int i=1;i<=kuai;i++){
		for(int j=i;j<=kuai;j++){
			p[i][j]=p[i][j-1]+num[j];
			for(int k=lk[j];k<=rk[j];k++){
				long long t=sum[j-1][n]-sum[j-1][a[k].x]-(sum[i-1][n]-sum[i-1][a[k].x]);
				p[i][j]+=t;
			}
		}
	}
	while(m--){
		long long l,r;
		long long ans=0;
		l=fr(),r=fr();
		l^=last,r^=last;
		int idl=idk[l],idr=idk[r];
		if(idl==idr){
			ans=kuainum[idl][l-lk[idl]+1][r-lk[idr]+1];
			last=ans;
			cout<<ans<<endl;
			continue;
		}
		ans=0;
		if(idl+1<=idr-1){
			ans=p[idl+1][idr-1];
		}
		ans+=kuainum[idl][l-lk[idl]+1][rk[idl]-lk[idl]+1];
        ans+=kuainum[idr][1][r-lk[idr]+1];
		if(idl+1<=idr-1){
			for(int i=lk[idr];i<=r;i++){
				ans+=sum[idr-1][n]-sum[idr-1][a[i].x]-(sum[idl][n]-sum[idl][a[i].x]);
			}
			for(int i=l;i<=rk[idl];i++){
				ans+=sum[idr-1][a[i].x-1]-sum[idl][a[i].x-1];
			}
		}
		int lt=lk[idr]-1,cnt=0;
		for(int i=lk[idl];i<=rk[idl];i++){
			if(b[i].id<l||b[i].id>r) continue;
			while(lt+1<=rk[idr]){
				if(b[lt+1].id<l||b[lt+1].id>r) lt++;
				else if(b[lt+1].x<b[i].x){
					cnt++,lt++;
				}
				else{
					break;
				} 
			}
			ans+=cnt;
		}
		last=ans;
		cout<<ans<<endl;
	}
	return 0;
}