BZOJ-3289: Mato的文件管理

Description

不带修改，查询区间逆序对个数。n,q<=50000

莫队+权值树状数组
树状数组维护区间中比当前数大的/小的有多少个。时间复杂度O(q√nlogn+n√nlogn)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,blo,a[51000],b[51000],c[51000],tot;
struct node
{
    int id,l,r;
}q[51000];
bool cmp(node x,node y)
{
    return x.l/blo==y.l/blo ? x.r<y.r : x.l<y.l;
}
int ans[51000],mx[51000],mi[51000];
int calc(int fl,int x,int z)
{
    int re=0,p;
    if(fl) {p=x-1; while(p>0) re+=mi[p],p-=-p&p;}
    else {p=x+1; while(p<=tot) re+=mx[p],p+=-p&p;}
    p=x; while(p>0) mx[p]+=z,p-=-p&p;
    p=x; while(p<=tot) mi[p]+=z,p+=-p&p;
    return re;
}
int main()
{
    scanf("%d",&n); blo=(int)sqrt(n)+1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    c[++tot]=b[1];
    for(int i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
    for(int i=1;i<=n;++i) a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int now=0,l=1,r=0;
    for(int i=1;i<=m;++i)
    {
        while(r<q[i].r) now+=calc(0,a[++r],1);
        while(l>q[i].l) now+=calc(1,a[--l],1);
        while(r>q[i].r) now-=calc(0,a[r--],-1);
        while(l<q[i].l) now-=calc(1,a[l++],-1);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}