bestcoder#45 1002 求区间的逆序数  树状数组

Dylans loves sequence

 

 Accepts: 250

 

 Submissions: 806

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

Dylans得到了NN个数a[1]...a[N]a[1]...a[N]。 有QQ个问题，每个问题形如(L,R)(L,R) 他需要求出L-RL−R这些数中的逆序对个数。 更加正式地，他需要求出二元组(x,y)(x,y)的个数，使得L \leq x,y \leq RL≤x,y≤R且x < yx
     
       a[y]a[x]>a[y]
     

输入描述

第一行有两个数NN和QQ。 第二行给出NN个数字a[1]...a[N]a[1]...a[N]。 接下来的QQ行，每行给出两个数L, R。 N \leq 1000,Q \leq 100000,L \leq R,1 \leq a[i] \leq 2^{31}-1N≤1000,Q≤100000,L≤R,1≤a[i]≤231−1

输出描述

对于每个询问，输出逆序对个数。

输入样例

3 23 2 11 21 3

输出样例

1 3 由于数据范围比较小，只有1000，所以n^2预处理+树状数组的插入统计就行了，复杂度nlogn.

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1100;const int INF=(1<<29);int n,q;ll a[maxn];ll b[maxn],m;int L,R;ll c[maxn];ll ans[maxn][maxn];int lowbit(int x){    return x&(-x);}ll sum(int p){    ll res=0;    while(p>0){        res+=c[p];        p-=lowbit(p);    }    return res;}void add(int p,int x){    while(p<=m){        c[p]+=x;        p+=lowbit(p);    }}int main(){    while(~scanf("%d%d",&n,&q)){        REP(i,1,n) scanf("%I64d",&a[i]),b[i]=a[i];        sort(b+1,b+n+1);        m=unique(b+1,b+n+1)-(b+1);        MS0(ans);        REP(i,1,n){            MS0(c);            REP(j,i,n){                int x=lower_bound(b+1,b+m+1,a[j])-b;                add(x,1);                ans[i][j]+=ans[i][j-1]+sum(m)-sum(x);            }        }        while(q--){            scanf("%d%d",&L,&R);            printf("%I64d\n",ans[L][R]);        }    }    return 0;}