已知有一个整数序列和一系列询问，每个询问是一个区间[l,r]。对于每个询问，输出该区间内逆序对个数

链接

BZOJ3289

题解

很明显可以使用莫队算法。首先对元素离散化，然后拿树状数组维护前缀和，每次利用树状数组更新答案。

算是莫队和树状数组的复习题。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 50010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define bit(x) (x&(-x))
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,cnt,q,Ans,block;
int a[N],b[N],pos[N],ans[N],s[N];

struct Data{
    int l,r,id;
}c[N];

map <int,int> M;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline bool cmp(const Data x,const Data y){return (pos[x.l]==pos[y.l])?x.r<y.r:x.l<y.l;}

inline int Query(int x,int y){
    int sum=0,Sum=0;
    x--;
    while (x){
        sum+=s[x];  x-=bit(x);
    }
    while (y){
        Sum+=s[y];  y-=bit(y);
    }
    return Sum-sum;
}

inline void Add(int x,int val){
    while (x<=n){
        s[x]+=val;  x+=bit(x);
    }
}

inline void update(int p,int flag,int add){
    if (flag){
        Ans+=add*Query(a[p]+1,cnt); Add(a[p],add);
    }   else {
        Ans+=add*Query(1,a[p]-1);   Add(a[p],add);
    }
}

inline void Solve(){
    int l=1,r=0,i=0;
    for (i=1;i<=q;i++){
        for (;r<c[i].r;r++) update(r+1,1,1);
        for (;r>c[i].r;r--) update(r,1,-1);
        for (;l<c[i].l;l++) update(l,0,-1);
        for (;l>c[i].l;l--) update(l-1,0,1);
        if (c[i].l==c[i].r) continue;
        ans[c[i].id]=Ans;
    }
}

int main(){
    n=read();
    for (i=1;i<=n;i++)  a[i]=b[i]=read();
    sort(b+1,b+1+n);
    for (i=1;i<=n;i++)
        if (!M[b[i]])   M[b[i]]=++cnt;
    for (i=1;i<=n;i++)  a[i]=M[a[i]];
    block=int(sqrt(n));
    for (i=1;i<=n;i++)  pos[i]=(i-1)/block+1;
    q=read();
    for (i=1;i<=q;i++){
        c[i].l=read();  c[i].r=read();  c[i].id=i;
    }
    sort(c+1,c+1+q,cmp);
    Solve();
    for (i=1;i<=q;i++)  printf("%d\n",ans[i]);
    return 0;
}