51nod 1019 逆序数(分治)

 

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input

第1行：N，N为序列的长度（n <= 50000) 第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

Output

输出逆序数

Input示例

4 2 4 3 1

Output示例

4

     题目意思很明确。前面的数字大于后面的有多少对。

 

     这道题可以用分治做，一般这种可以分区计算结果后处理的都可以用分治。简单说下分治

     1：把范围分为尽量相等的两个区域，分别对两个区域计算结果

     2：把分开的区域再分，得到两半区域结果进行处理。

     那么对于本题目：

    　1：对范围一直递归，直到有一半只有一个元素（最小范围开始想），对面左边区域与右边区域的逆序对

　　　　　　　　比如：　左区域：１　右区域：３，２，答案为２对。（３，２）不算，因为同区域

　　２：计算完进行排序，方便上一层的计算，排序不影响上一层的运算，因为运算涉及两个区间，左区域排序后还是在右区域的左边

　　　　　　　　　　　　　　　　　　这个很难说，自己理解一下过程就觉得很有趣了，做个例子

　　　　　　　　３　１　４　２　５　　分区域：　　　　　　　　　　　　　　　　　　　　左边：　３　１　右边，４　２　５　

　　　　左边进行运算，３＞１　答案加一。加完排序：　　　　　　　　　　　　　　　　于是左边：　１　３

　　　　右边进行运算，分为　　左边：４　右边：２　５　　因为４＞２，答案加一。　　　　　　　　　　　　排序：２　４　５

　　　　两边运算完成，返回上一层：１　３　２　４　５，分为两半运算（子区域已经运算完成）：左：１　３　右边　２　４　５

　　　　３＞２，答案加一，排序：　１　２　３　４　５。再把以这５个数为分区域的区域运算。

　　　　代码献上：

　　　　

#include <iostream> #include <cstdio> #include <string.h> #include <fstream> #include <algorithm> using namespace std; int ans=0,a[50005],temp[50005],i,j,n,ok=0; void fenzhi(int l,int r) { int mid,t1,t2,t3=0,t4; if(r-l>1) { mid=l+(r-l)/2; t4=mid; fenzhi(l,t4); fenzhi(t4,r); t2=mid; t3=0; for(t1=l;t1<mid;t1++) { // cout<<"ok"; for(;t2<r;t2++) { if(a[t2]>=a[t1]) { temp[t3++]=a[t1]; ans+=t2-mid; break; } temp[t3++]=a[t2]; } // cout<<" ok"; if(t2==r) { ans+=(mid-t1)*(r-mid); for(t4=t1;t4<mid;t4++) temp[t3++]=a[t4]; break; } } for(t1=l;t1<r;t1++) a[t1]=temp[t1-l]; // sort(a+l,a+r); } } int main() { cin>>n; for(i=0;i<n;i++) cin>>a[i]; fenzhi(0,n); cout<<ans; return 0; }