题目

输入格式：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

数据范围：

对于50%的数据，n≤2500

对于100%的数据，n≤40000。

分析

使用分治的思想将序列不断分为两段，然后将这两段进行归并排序，因为每段已经排好序，所有每次增加的逆序对个数即为第一个（有序序列长度-需合并的位置+1）

同时我们还可以用树状数组求解，我们按大小排序，依次插入到它原本所在位置，所以逆序对个数即为在它之前插入的位置比它靠后的数的总个数

代码

归并排序版

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int a[100000],t[100000];

int ans;

void mer(int le,int mid,int ri){

      int i=le,j=mid+1,k=le;

      while(i<=mid&&j<=ri){

          if(a[i]>a[j]){

              t[k++]=a[j++];

              ans+=(mid-i+1);

          }else t[k++]=a[i++];

      }

      for(i;i<=mid;i++)t[k++]=a[i];

      for(j;j<=ri;j++)t[k++]=a[j];

      for(i=le;i<=ri;i++)a[i]=t[i];

}

void go(int le,int ri){

      if(le<ri){

          int mid=(le+ri)>>1;

          go(le,mid);

          go(mid+1,ri);

          mer(le,mid,ri);

      }

}

int main(){

      int n,m,i,j,k;

      cin>>n;

      for(i=1;i<=n;i++){

          cin>>a[i];

      }

      go(1,n);

      cout<<ans<<endl;

      return 0;

}

树状数组版

#include<bits/stdc++.h>

using namespace std;

inline void read(int &x){

      int f=1;x=0;char s=getchar();

      while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

      while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}

      x*=f;

}

struct node {

      int pl,d;

}a[110000];

int c[110000],n;

inline bool cmp(const node &x,const node &y){return x.d<y.d;}

inline int lb(int x){return x&(-x);}

inline void add(int x,int k){while(x<=n)c[x]+=k,x+=lb(x);}

inline int q(int x){int ans=0;while(x)ans+=c[x],x-=lb(x);return ans;}

int main()

{     int i,ans=0;

      read(n);

      for(i=1;i<=n;i++){

         read(a[i].d);

         a[i].pl=i;

      }

      sort(a+1,a+n+1,cmp);  

      for(i=1;i<=n;i++){

           add(a[i].pl,1);

           ans+=i-q(a[i].pl-1)-1;

      }

      printf("%d\n",ans);

      return 0;

}