目录
归并排序
树状数组
线段树
ACM题刷多了，逆序数应该都会求了，今天就说一下逆序数的三种求法
归并排序归并排序应该是用的最多的了，其思路为：
对某个序列进行归并，在前半部分和后半部分两段子序列进行归并时，比较两个子序列首元素中较小者。而当前半部分首元素大于后半部分时，就产生了逆序，子序列2的首元素下标减去已归并的元素数量就是该元素的逆序，代码如下：
#include <stdio.h>#include <string.h>#define MAXN 50010long long s[MAXN];long long num[MAXN];long long cnt;//归并排序 void merge( int start , int mid , int end ) {int i = start;int j = mid + 1;int k = start;// printf( "111cnt=%dn",cnt );while( i<=mid && j<=end ) {if( num[i]<=num[j] )s[k++] = num[i++];else {cnt += j-k;s[k++] = num[j++];}}while( i<=mid ) {s[k++] = num[i++];}while( j<=end ) {s[k++] = num[j++];}for( i=start ; i<=end ; i++ )num[i] = s[i];}//将数组一分为2 void mergeSort( int start , int end ) {if( start>=end )return;// printf( "222cnt=%dn",cnt );int mid = ( start+end )/2;mergeSort( start,mid );mergeSort( mid+1,end );merge( start,mid,end );}int main() {// freopen( "input.txt","r",stdin );int n;while( ~scanf( "%d",&n ) ) {memset( num,0,sizeof(num) );for( int i=0 ; i<n ; i++ ) {scanf( "%d",&num[i] );}cnt = 0;mergeSort( 0,n-1 );printf( "%lldn",cnt );}} 树状数组树状数组作为一种常用的数据结构，也能被用作计算一个序列的逆序数，步骤如下：
首先，树状数组的长度得是输入的序列元素的范围，我们假设一个数组num，存储输入的序列，然后一个数组f，数组f的含义为：如果序列中出现过元素n，那么就令f[n]=1；反之则为0。此时，树状数组tr记录的便是从1~n中出现过多少个树，因此，要求得n的逆序数，我们只需求出已出现的数的数目，减去小于n的数出现的数目，便是大于当前数的数目，即n的逆序。代码实现如下：
#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n;int num[5050],tr[5051];int lowbit( int x ){return x & -x;}void insert( int pos , int v ){for( ; pos<=5050 ; pos += lowbit( pos ) )tr[pos] += v;}int query( int pos ){int ans = 0;while( pos ){ans += tr[pos];pos -= lowbit( pos );}return ans;}int main(){// freopen( "in.txt","r",stdin ); std::ios::sync_with_stdio( false );int v,ans,cnt;while( cin >> n ){memset( num,0,sizeof(num) );memset( tr,0,sizeof(tr) );ans = 0;for( int i=1 ; i<=n ; i++ ){cin >> num[i];ans += query( n+1 ) - query( num[i]+1 );insert( num[i]+1,1 );}cnt = ans;cout << ans << endl;}} 线段树线段树思想同树状数组，每次查询比当前树大的数的出现次数就是当前数的逆序
#include <iostream>#include <cstring>#include <algorithm>using namespace std;int num[5051];typedef struct segNode{int cnt;int left,right;struct segNode *lchild,*rchild;segNode(){this->cnt = 0;this->left = this->right = 0;this->lchild = this->rchild = NULL;}} *ST;void build( int s , int e , ST &T ){if( T==NULL )T = new segNode();T->cnt = 0;T->left = s;T->right = e;if( s==e )return ;int mid = ( s+e )/2;build( s,mid,T->lchild );build( mid+1,e,T->rchild );}void updata( ST &T , int pos ){if( T->left == T->right ){T->cnt++;return;}int mid = ( T->left + T->right ) / 2;if( pos<=mid)updata( T->lchild,pos );elseupdata( T->rchild,pos );T->cnt = T->lchild->cnt + T->rchild->cnt;}int query( ST T , int s , int e ){if( T->left==s && T->right==e ){return T->cnt;}int mid = ( T->left + T->right ) / 2;int ans = 0;if( e<=mid ){ ans += query( T->lchild,s,e );}else if( s>=mid+1 ){ans += query( T->rchild,s,e );}else{ans += query( T->lchild,s,mid );ans += query( T->rchild,mid+1,e );}return ans;}int main(){// freopen( "in.txt","r",stdin );// std::ios::sync_with_stdio( false );int n,ans;ST T;while( cin >> n ){memset( num,0,sizeof(num) );T = new segNode();build( 0,n-1,T );ans = 0;for( int i=0 ; i<n ; i++ ){cin >> num[i];ans += query( T,num[i],n-1 );updata( T,num[i] );} cout << ans << endl;}}