# 归并排序求逆序数

```#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 30100;

LL a[maxn];
LL temp[maxn];
LL sum;

struct node
{
LL y1;
LL y2;
int id;
}f[maxn];

void Merge(LL a[], int l, int mid, int r)
{
int begin1 = l;
int end1 = mid;
int begin2 = mid+1;
int end2 = r;
int k = 0;
while(begin1 <= end1 && begin2 <= end2)
{
if(a[begin1] < a[begin2])
{
temp[k++] = a[begin1];
begin1++;
sum += begin2-(mid+1);
}
else
{
temp[k++] = a[begin2];
begin2++;
}
}
while(begin1 <= end1)
{
temp[k++] = a[begin1];
begin1++;
sum += end2-mid;
}
while(begin2 <= end2)
{
temp[k++] = a[begin2];
begin2++;
}
for(int i = l; i <= r; i++) a[i] = temp[i-l];
}

void MergeSort(LL a[], int l, int r)
{
int mid = (l+r)>>1;
if(l < r)
{
MergeSort(a, l, mid);
MergeSort(a, mid+1, r);
Merge(a, l, mid, r);
}
}
```

## poj2299解题报告（归并排序求逆序数）

POJ 2299,题目链接http://poj.org/problem?id=2299 题意: 给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列. 思路: 其实就是求逆序数,那么直接向到的就是冒泡了,交换一次,记录一次即可.但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时. 然后...发现曾经微软有一道笔试题类似就是求逆序数的,对,没错,用归并. 例:合并两个序列(1,3,5)(2,4,6),新序列第二个元素是2,那么它和它前面的3.5形成了逆序数对

## POJ 2299 Ultra-QuickSort (求逆序数：离散化+树状数组或者归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 55048   Accepted: 20256 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

## 归并排序 求逆序数 链表的归并排序 多线程归并排序 java

import java.util.Scanner; public class Main { private static int count=0; public static void mergesort(int a[],int low,int high) { if(low<high) { int mid=(low+high)>>1; mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,mid,high); } } pri

## E - 归并排序 求逆序数

Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to

## 归并排序求逆序数对。

1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 int high[100010]; 7 int temp[100010]; 8 int angry[100010]; 9 int num; 10 void mergesort(int first,int mid,int last) 11 { 1