树状数组求逆序对个数

理论阐述

树状数组的优越性

暴力求逆序对的方法就是利用双指针的移动，时间复杂度为$O(n^2)$，而树状数组能在$O(n\log n)$内完成逆序对个数的求解。

树状数组使用方法

用$a[i]$存储出现的数，用树状数组$c$统计比$a[i]$小的数。顺序读取$a[i]$，每一次都将比$a[i]$小的数的个数增加$1$，即$add(a[i],1)$，然后将逆序对个数加上$i-query(a[i])$。

举例

有$5$个数，分别为$5,3,4,2,1$，当读入数据$5$时，$c=[0,0,0,0,1]$；当读入数据$3$时，$c=[0,0,1,1,1]$；当读入数据$4$时，$c=[0,0,1,2,1]$$...$

离散化

当数列中元素的大小分布很分散，普通数组根本无法存下，这时候就需要进行离散化处理。
就比如将数列$initial=[212,9,9,1000000232,98989,99999993249322]$离散化成为$discretization=[2,1,1,4,3,5]$，逆序对个数是不变的。

例题

HDU 1394 Minimum Inversion Number

Problem Description

The inversion number of a given number sequence $a_1, a_2, ..., a_n$ is the number of pairs $(a_i, a_j)$ that satisfy $i < j$ and $a_i > a_j$.
For a given sequence of numbers $a_1, a_2, ..., a_n$, if we move the first $m >= 0$ numbers to the end of the seqence, we will obtain another sequence. There are totally $n$ such sequences as the following:
$a_1, a_2, …, a_{n-1}, a_n $(where $m = 0$ - the initial seqence)
$a_2, a_3, …, a_n, a_1 $(where $m = 1$)
$a_3, a_4, …, a_n, a_1, a_2 $(where $m = 2$)
$...$
$a_n, a_1, a_2, ..., a_{n-1}$ (where $m = n-1$)
You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer $n (n <= 5000)$; the next line contains a permutation of the $n$ integers from $0$ to $n-1$.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

10
1 3 6 9 0 8 5 7 4 2

Sample Output

16

Translation

给一个长度为$n$的数列，数列中的元素是${\text{0}} \sim n - 1$，将数列的前$m(m \in [0,n-1])$项删去，拼接到数列的末尾，加上初始数列共能得到$n$个数列，求这$n$个数列中逆序对最少的数列的逆序对个数。

Idea

先用树状数组求原始数列的逆序对。
当数列第一个元素$a[1]$时，逆序对个数增加$n-a[1]$（比$a[1]$大的元素），减少$a[1]-1$（比$a[1]$小的元素），因此只要遍历数组求出剩余所有数列的逆序对个数即可。

Code

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5004;
int a[N],c[N];
int n;
int lowbit(int x)
{
	int res=x&(-x);
	return res;
}
void add(int i,int val)
{
	while(i<=n)
	{
		c[i]+=val;
		i+=lowbit(i);
	}
}
int query(int i)
{
	int res=0;
	while(i>=1)
	{
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}
void solve()
{
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	int i;
	int res=0;
	int ans=0x3f3f3f3f;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		//lowbit(0)不允许更新，因此将每一个a[i]加上1
		add(++a[i],1);
		res=res+i-query(a[i]);
	}
	ans=min(ans,res);
	for(i=1;i<=n;i++)
	{
		//增加和减少的效应相加
		res=res-(a[i]-1)+(n-a[i]);
		ans=min(ans,res);
	}
	cout<<ans<<endl;
}
int main()
{
	while(cin>>n) solve();
	return 0;
}

HDU 4911 Inversion

Problem Description

bobo has a sequence $a_1,a_2,…,a_n$. He is allowed to swap two adjacent numbers for no more than $k$ times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair $(i,j)$ where $1≤i<j≤n$ and $a_i>a_j$.

Input

The input consists of several tests. For each tests:
The first line contains $2$ integers $n,k (1≤n≤10^5,0≤k≤10^9)$. The second line contains $n$ integers $a_1,a_2,…,a_n (0≤a_i≤10^9)$.

Output

For each tests:
A single integer denotes the minimum number of inversions.

Sample Input

3 1
2 2 1
3 0
2 2 1

Sample Output

1
2

Translation

给定一个序列，有k次机会交换相邻两个位置的数，问说最后序列的逆序对数最少为多少。

Idea

按照最有利的策略，每交换一个相邻数对可将逆序对的个数减少$1$，交换$k$次就能将逆序对个数减少$k$；若初始数列逆序对的个数小于等于$k$，那么一定能在使用不多于$k$次的交换次数，使得数列逆序对个数降低至$0$。
此题的$a_i\in [0,10^9]$（小心不要爆int），而最多只有$10^5$个$a_i$，有必要进行离散化。

Code

#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define dc discretization //Translation：离散化
using namespace std;
const int N=100005;
ll initial[N];//初始数组 
ll c[N];//树状数组
ll dc[N];//离散化数组 
ll n,k;
ll lowbit(int x)
{
	ll res=x&(-x);
	return res;
}
void add(ll i,ll val)
{
	while(i<=n)
	{
		c[i]+=val;
		i+=lowbit(i);
	}
}
ll query(ll i)
{
	ll res=0;
	while(i>=1)
	{
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}
void solve()
{
	memset(c,0,sizeof(c));
	ll i;
	ll ans=0;
	for(i=1;i<=n;i++)
	{
		cin>>initial[i];
		dc[i]=++initial[i];
	}
	sort(dc+1,dc+1+n);
	ll len;
	len=unique(dc+1,dc+1+n)-(dc+1);
	for(i=1;i<=n;i++)
	{
		ll pos;
		pos=lower_bound(dc+1,dc+1+len,initial[i])-dc;
		add(pos,1);
		ans=ans+i-query(pos);
	}
	cout<<max(ans-k,0LL)<<endl;
}
int main()
{
	while(cin>>n>>k) solve();
	return 0;
}