第二个点过不去 /kel

提交记录：https://www.luogu.com.cn/record/45468051

以下是 3.3kb 的 /shit 山代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=1e5+5,B=200;
typedef long long ll;
ll blo[N/B+5][N/B+5],sum;
int n,a[N],t[N],b[N],L[N],R[N];
int ccnt[N/B+5][N],bl[N],tr[N],pre[N],suf[N];
int c[N];
inline int rd(){
	int x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x;
}
inline void write(ll x){
	if(x>=10) write(x/10);putchar(x%10+'0');
}
inline void merge(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	merge(l,mid),merge(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r)
		if(a[i]<=a[j]) t[k++]=a[i++];
		else sum+=(mid-i+1),t[k++]=a[j++];
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	for(int i=l;i<=r;++i) a[i]=t[i];
}
inline void solve(register int L1,register int R1,register int L2,register int R2){
	sum=0;
	register int i=L1,j=L2;
	while(i<=R1 && j<=R2)
		if(a[i]<=a[j]) i++;
		else sum+=(R1-i+1),j++;
}
inline void add(int x,short c){
	while(x<=n) tr[x]+=c,x+=(x&-x);
}
inline int query(int x){
	int res=0;
	while(x) res+=tr[x],x-=(x&-x);
	return res;
}
inline ll calc(int l,int r){
	ll ans=0;
	if(bl[l]==bl[r]){
		int tot=l;
		for(register int i=L[bl[l]];i<=R[bl[l]];++i)
			if(c[i]>=l && c[i]<=r) a[tot]=b[c[i]],++tot;
		tot=L[bl[l]];
		for(register int i=L[bl[l]];i<=R[bl[l]];++i)
			if(c[i]<l) a[tot]=b[c[i]],++tot;
		sum=0; solve(L[bl[l]],l-1,l,r);
		ans=pre[r]-((l-1>=L[bl[l]])?pre[l-1]:0)-sum;
		return ans;
	}
	ans=blo[bl[l]+1][bl[r]-1]+pre[r]+suf[l];
	for(register int i=l;i<=R[bl[l]];++i)
		a[i]=b[i],ans+=ccnt[bl[r]-1][a[i]]-ccnt[bl[l]][a[i]];
	ans+=1ll*(R[bl[r]-1]-L[bl[l]+1]+1)*(r-L[bl[r]]+1);
	for(register int i=L[bl[r]];i<=r;++i)
		a[i]=b[i],ans-=(ccnt[bl[r]-1][a[i]]-ccnt[bl[l]][a[i]]);
	int tot=l;
	for(register int i=L[bl[l]];i<=R[bl[l]];++i)
		if(c[i]>=l) a[tot]=b[c[i]],++tot;
	tot=L[bl[r]];
	for(register int i=L[bl[r]];i<=R[bl[r]];++i)
		if(c[i]<=r) a[tot]=b[c[i]],++tot;
	sum=0; solve(l,R[bl[l]],L[bl[r]],r); ans+=sum;
	return ans;
}
bool cmp(int i,int j){
	return b[i]<b[j];
}
signed main(){
//	freopen("data1.in","r",stdin);
//	freopen("data1.out","w",stdout);
	n=rd();int m=rd();
	for(int i=1;i<=n;++i)
		a[i]=rd(),b[i]=a[i],c[i]=i;
	int cnt=0,pos=0;
	while(pos<n) ++cnt,L[cnt]=R[cnt-1]+1,pos=R[cnt]=min(n,L[cnt]+B-1);	
	for(int i=1;i<=n;++i)
		bl[i]=(i-1)/B+1;
	for(register int u=1;u<=cnt;++u){
		sort(c+L[u],c+R[u]+1,cmp);
		for(register int i=L[u];i<=R[u];++i){
			if(i^L[u]) pre[i]=pre[i-1];
			pre[i]+=(i-L[u])-query(a[i]);
			add(a[i],1);
		}
		for(register int i=L[u];i<=R[u];++i) add(a[i],-1);
		for(register int i=R[u];i>=L[u];--i){
			if(i^R[u]) suf[i]=suf[i+1];	
			suf[i]+=query(a[i]);
			add(a[i],1);		
		}
		for(register int i=L[u];i<=R[u];++i) add(a[i],-1);
	}
	for(int i=1;i<=cnt;++i)
		sum=0,merge(L[i],R[i]),blo[i][i]=sum;
	for(int len=2;len<=cnt;++len)
		for(int i=1;i+len-1<=cnt;++i){
				int j=i+len-1;
				blo[i][j]=blo[i+1][j]+blo[i][j-1]-blo[i+1][j-1];
				solve(L[i],R[i],L[j],R[j]),blo[i][j]+=sum;
			}
	for(register int u=1;u<=cnt;++u){
		for(register int i=L[u];i<=R[u];++i)
			++ccnt[u][a[i]];
		for(register int i=1;i<=n;++i)
			ccnt[u][i]+=ccnt[u][i-1];
		for(register int i=1;i<=n;++i)
			ccnt[u][i]+=ccnt[u-1][i];
	}
	ll ans=0;
	int l,r;
	while(m--){
		l=rd()^ans,r=rd()^ans;
		ans=calc(l,r);
		write(ans),puts("");
	}
	return 0;
}