[文章目录]
Description
给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。n<=5*10^4 m<=5*10^4
还是预处理整块的答案O(n√nlogn)，并统计每个块的前缀中比每个权值大、小的权值个数O(n√n)
询问的时候将零散部分单独计算，整块答案直接拿出来，之后累计零散部分与整块部分的答案【即整块里比当前大/小的个数】。
复杂度O(n√nlogn)
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50100
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
return x;
}
int n,m,bl,a[N],b[N],c[N],tot;
int f[230][230],g[N][230],bi[N];
void fix(int x,int y) {while(x>0) bi[x]+=y,x-=-x&x;}
int query(int x) {int re=0; while(x<=tot) re+=bi[x],x+=-x&x; return re;}
int main()
{
n=read();
int i; bl=(int)sqrt(n)+1;
for(i=0;i<n;++i) b[i]=a[i]=read();
sort(b,b+n);
for(c[++tot]=b[0],i=1;i<n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(i=0;i<n;++i) a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
int l,r,now;
for(l=0;l<n;l+=bl)
{
memset(bi,0,sizeof bi);
for(now=0,i=l,r=l+bl-1;i<n;++i)
{
now+=query(a[i]+1);
fix(a[i],1);
if(i==r) f[l/bl][r/bl]=now,r+=bl;
}
}
memset(b,0,sizeof b);
for(l=0,r=bl-1;l<n;++l)
{
b[a[l]]++;
if(l==r) for(r+=bl,i=1;i<=tot;++i) g[i][l/bl]=g[i-1][l/bl]+b[i];
}
m=read(); unsigned int ans=0; int L,R;
memset(bi,0,sizeof bi);
while(m--)
{
l=read()^ans; r=read()^ans; --l,--r;
if(r-l+1<=2*bl)
{
for(ans=0,i=l;i<=r;++i)
{
ans+=query(a[i]+1);
fix(a[i],1);
}
printf("%u\n",ans);
for(i=l;i<=r;++i) fix(a[i],-1);
}
else
{
L= l%bl==0 ? l/bl : l/bl+1;
R= r%bl==bl-1 ? r/bl :r/bl-1;
ans=f[L][R];
for(i=l;i<L*bl;++i) ans+= L ? g[a[i]-1][R]-g[a[i]-1][L-1] : g[a[i]-1][R];
for(i=r;i>=R*bl+bl;--i) ans+= (R-L+1)*bl-(L ? g[a[i]][R]-g[a[i]][L-1] : g[a[i]][R]);
for(i=l;i<L*bl;++i)
{
ans+=query(a[i]+1);
fix(a[i],1);
}
for(i=R*bl+bl;i<=r;++i)
{
ans+=query(a[i]+1);
fix(a[i],1);
}
for(i=l;i<L*bl;++i) fix(a[i],-1);
for(i=R*bl+bl;i<=r;++i) fix(a[i],-1);
printf("%u\n",ans);
}
}
return 0;
}