rt，自己想的，复杂度未知，目前全RE

思路是：

考虑各种贡献

1. 散块对散块/散块内部——暴力树状数组

2. 散块对整块——预处理 $p1[i][j]$ 表示第 $i$ 个块中小于 $j$ 的数的个数

3. 整块对散块——类似，预处理 $p2[i][j]$ 表示第 $i$ 块中大于 $j$ 的数的个数

4. 整块对整块——预处理 $f[i][j]$ 表示第 $i$ 块到第 $j$ 块的逆序对个数

对 $p1$ 和 $p2$ 求前缀和（指例如：$sum1[i][j]$ 表示前 $i$ 块小于 $j$ 的数的个数，$sum2$ 同理

目前样例已过，但是交上去全RE，有时TLE，求各位大佬：

• 优化复杂度

• 帮我解决下RE

如果违规@我一下，紫衫

预处理部分见注释

代码：

#include<bits/stdc++.h>
#define Max(x,y) (x>y?x:y)
using namespace std;
const int N=1e5+5,ghN=320;
int n,m,block,tot,a[N],p1[ghN][N],p2[ghN][N],sum1[ghN][N],sum2[ghN][N],L[ghN],R[ghN],belong[N],c[N];
long long f[ghN][ghN],lastans,l,r;
#define lowbit(x) (x&-x)
inline void update(int x){for(;x<=n;x+=lowbit(x))c[x]++;}
inline long long query(int x){long long ans=0;for(;x;x-=lowbit(x))ans+=1ll*c[x];return ans;}
inline void del(int x){for(;x<=n;x+=lowbit(x))c[x]--;}
void init()
{
	block=sqrt(n);
	tot=(n-1)/block+1;
	for(register int i=1;i<=tot;i++)
		L[i]=R[i-1]+1,R[i]=i*block;
	R[tot]=n;
	for(register int i=1;i<=tot;i++)
	{
		int maxx=0;
		for(register int j=L[i];j<=R[i];j++)
		{
			belong[j]=i;
          //对于这一部分不难发现是区间加，差分一下
			p1[i][a[i]+1]--;
			p1[i][n+1]++;
			p2[i][0]--;
			p2[i][a[i]]++;
			maxx=Max(maxx,a[j]);//这个块里的数的最大值，等会对差分数组做前缀和只需要跑到这里
		}
		for(register int j=1;j<=maxx;j++)
			p1[i][j]+=p1[i][j-1],p2[i][j]+=p2[i][j-1];
		for(register int j=1;j<=n;j++)//对p1,p2求前缀和
			sum1[i][j]=sum1[i-1][j]+p1[i][j],sum2[i][j]=sum2[i-1][j]+p2[i][j];
	}
	for(register int i=1;i<=tot;i++)
	{
		for(register int j=i+1;j<=tot;j++)
		{
          //这一部分我的思路是这样的：
          //首先枚举块，显然[i,j]包含了[i,j-1]，那么[i,j-1]的答案不用白不用，只需要计算这个块里的数与前面的数产生的逆序对再相加
			f[i][j]=f[i][j-1];
			for(register int k=R[j];k>=L[j];k--)
			{
				f[i][j]+=query(a[k]);
				update(a[k]);
			}
		}
		for(register int j=i+1;j<=tot;j++)
		{
			for(register int k=L[j];k<=R[j];k++)
			{
				del(a[k]);
			}
		}
	}
	return;
}
long long query(int l,int r)
{
	long long ans=0;
	if(belong[l]==belong[r])
	{
      //块内暴力
		for(register int i=r;i>=l;i--)
		{
			ans+=query(a[i]);
			update(a[i]);
		}
		for(register int i=l;i<=r;i++)
			del(a[i]);//清空
		return ans;
	}
	int p=belong[l],q=belong[r];
	//整块对整块
	ans+=f[p+1][q-1];
	//散块对整块
  //这里由于求了前缀和，直接相减
	for(register int i=l;i<=R[p];i++)
		ans+=1ll*(sum1[q-1][a[i]]-sum1[p][a[i]]);
	//整块对散块
  //同理
	for(register int i=r;i>=L[q];i--)
		ans+=1ll*(sum2[q-1][a[i]]-sum2[p][a[i]]);
	//散块对散块/散块内部
  //散块对散块和散块内部的前缀和直接暴力
	for(register int i=r;i>=L[q];i--)
		ans+=query(a[i]),update(a[i]);
	for(register int i=R[p];i>=l;i--)
		ans+=query(a[i]),update(a[i]);
	//清空
	for(register int i=l;i<=R[p];i++)
		del(a[i]);
	for(register int i=r;i>=L[q];i--)
		del(a[i]);
	return ans;
}
int main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
  //本来是手写IO优化的，但是本地运行不了，就先写了cin
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;i++)cin>>a[i];
	init();
	for(;m;--m)
	{
		cin>>l>>r;
		l^=lastans,r^=lastans;
	    cout<<(lastans=query(l,r))<<endl;
	}
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}