求逆序数的两个方法

1.归并排序

#include 

using namespace std;

const int maxn = 1000;

int a[maxn],b[maxn];
int ans;

void merge_sort(int x,int y){
    if(y-x>1)
    {
        int m = x+(y-x)/2;
        int p = x, q = m,i = x;
        merge_sort(x,m);
        merge_sort(m,y);
        while(py){
            if(q>=y||(p];
            else {b[i++]=a[q++];ans+=m-p;}
        }
        for(int i = x;i b[i];
    }
}

int main()
{
    int n;
    while(cin>>n){
       for(int i=0;i>a[i];
       ans=0;
       merge_sort(0,n);
       cout<endl;
       for(int i=0;i" ";cout<<endl;
    }
    return 0;
}

2.离散+树状数组

E. Infinite Inversions time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

There is an infinite sequence consisting of all positive integers in the increasing order: p?=?{1,?2,?3,?...}. We performed n swap operations with this sequence. A swap(a,?b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i,?j), that i?<?j and pi?>?pj.

Input

The first line contains a single integer n (1?≤?n?≤?105) — the number of swap operations applied to the sequence.

Each of the next n lines contains two integers ai and bi (1?≤?ai,?bi?≤?109, ai?≠?bi) — the arguments of the swap operation.

Output

Print a single integer — the number of inversions in the resulting sequence.

Sample test(s) input

2
4 2
1 4

output

4

input

3
1 6
3 4
2 5

output

15

Note

In the first sample the sequence is being modified as follows: . It has 4 inversions formed by index pairs (1,?4), (2,?3), (2,?4) and (3,?4).

离散：

逆序数组：9 1  0 5 4 --> 5 2 1 4 3

这题有点特别：就是先把那些交换的点+那些中间的点（等价的几个，所以a[i].yy可能大于1）

注意：maxn要为4*1e5，因为不单只2倍的10的5次方操作!

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include