题目
题目链接：https://www.luogu.com.cn/problem/P5047
给你一个长为 (n) 的序列 (a)，(m) 次询问，每次查询一个区间的逆序对数。
(n,mleq 10^5)，空间限制 (
m 31.25MB)。
思路
二次离线莫队板子。
考虑莫队时从区间 ([l,r]) 变为区间 ([l,r+1]) 时的影响。答案显然增加了“区间 ([l,r]) 中比 (r+1) 大的数的数量”。差分一下就是区间 ([1,r]) 中大于 (r+1) 的数的数量，减去区间 ([1,l-1]) 中大于 (r+1) 的数的数量。
前者可以直接用树状数组求出来。考虑如何处理后者。
再次离线，等价于有 (O(nsqrt{n})) 个询问，每个询问形如“求 ([1,l]) 中有多少个数大于 (r)”。对于每一个这样的询问，扔进 (l) 的 vector 中。然后从 (1) 到 (n) 枚举 (l)，并处理每一个询问。
这里如果直接用树状数组的话就和在线复杂度一样了，都是 (O(nsqrt{n}log n))。注意到询问是 (O(nsqrt{n}))，但是加点只有 (O(n))，所以采用分块，实现 (O(sqrt{n})) 修改，(O(1)) 查询。
当然询问也可能是“求 ([r,n]) 中有多少个数小于 (l)”，反过来也搞一下即可。
这样的话时间复杂度是降至 (O((n+m)sqrt{n})) 了，但是空间也是 (O(nsqrt{n})) 的。注意到瓶颈在于询问的数量，在莫队中，对于每一个询问，左右端点都会连续的移动，所以可以把一个端点不变时，另一个端点的移动区间加入 vector，这样的话空间就是 (O(m)) 的了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,M=320;
int n,m,B,a[N],b[N],bel[N];
ll cnt1[N],cnt2[N],ans[N],sum1[N],sum2[N];
int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
struct node
{
int l,r,id;
}ask[N];
vector<node> L[N],R[N];
bool cmp(node x,node y)
{
if (bel[x.l]!=bel[y.l]) return x.l<y.l;
return x.r<y.r;
}
struct BIT
{
int c[N];
void add(int x,int v)
{
for (int i=x;i<=n;i+=i&-i)
c[i]+=v;
}
int query(int x)
{
int ans=0;
for (int i=x;i;i-=i&-i)
ans+=c[i];
return ans;
}
}bit;
int main()
{
n=read(); m=read(); B=sqrt(n);
for (int i=1;i<=n;i++) a[i]=b[i]=read();
sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;
for (int i=1;i<=n;i++)
{
bel[i]=(i-1)/B+1;
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
cnt1[i]=cnt1[i-1]+bit.query(n-a[i]);
bit.add(n-a[i]+1,1);
}
memset(bit.c,0,sizeof(bit.c));
for (int i=n;i>=1;i--)
{
cnt2[i]=cnt2[i+1]+bit.query(a[i]-1);
bit.add(a[i],1);
}
cnt1[n+1]=cnt1[n]; cnt2[0]=cnt2[1];
for (int i=1;i<=m;i++)
ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
sort(ask+1,ask+1+m,cmp);
for (int i=1,l=1,r=0;i<=m;i++)
{
if (l>ask[i].l)
{
ans[ask[i].id]+=cnt2[ask[i].l]-cnt2[l];
R[r+1].push_back((node){ask[i].l,l-1,-ask[i].id}); l=ask[i].l;
}
if (r<ask[i].r)
{
ans[ask[i].id]+=cnt1[ask[i].r]-cnt1[r];
L[l-1].push_back((node){r+1,ask[i].r,-ask[i].id}); r=ask[i].r;
}
if (l<ask[i].l)
{
ans[ask[i].id]-=cnt2[l]-cnt2[ask[i].l];
R[r+1].push_back((node){l,ask[i].l-1,ask[i].id}); l=ask[i].l;
}
if (r>ask[i].r)
{
ans[ask[i].id]-=cnt1[r]-cnt1[ask[i].r];
L[l-1].push_back((node){ask[i].r+1,r,ask[i].id}); r=ask[i].r;
}
}
for (int i=1;i<=n;i++)
{
int val=a[i];
for (int j=1;j<bel[val];j++) sum1[j]++;
for (int j=B*(bel[val]-1)+1;j<val;j++) sum2[j]++;
for (int j=0;j<(int)L[i].size();j++)
{
int id=abs(L[i][j].id),f=(L[i][j].id<0)?-1:1;
for (int k=L[i][j].l;k<=L[i][j].r;k++)
ans[id]+=f*(sum1[bel[a[k]]]+sum2[a[k]]);
}
}
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
for (int i=n;i>=1;i--)
{
int val=n-a[i];
for (int j=1;j<bel[val];j++) sum1[j]++;
for (int j=B*(bel[val]-1)+1;j<val;j++) sum2[j]++;
for (int j=0;j<(int)R[i].size();j++)
{
int id=abs(R[i][j].id),f=(R[i][j].id<0)?-1:1;
for (int k=R[i][j].l;k<=R[i][j].r;k++)
ans[id]+=f*(sum1[bel[n-a[k]]]+sum2[n-a[k]]);
}
}
for (int i=1;i<=m;i++)
ans[ask[i].id]+=ans[ask[i-1].id];
for (int i=1;i<=m;i++)
cout<<ans[i]<<"
";
return 0;
}