樹狀數組求逆序對 - 手套

手套

描述

你現在有N對手套，但是你不小心把它們弄亂了，需要把它們整理一下。N對手套被一字排開，每隻手套都有一個顔色，被記為0~N-1，你打算通過交換把每對手套都排在一起。由于手套比較多，你每次隻能交換相鄰兩個手套。請你計算最少要交換幾次才能把手套排整齊。

輸入

輸入第一行一個N，表示手套對數。

第二行有2N個整數，描述了手套的顔色。每個數都在0~N-1之間，且每個數字都會出現恰好兩次。

輸出

一行，包含一個數，表示最少交換次數。

樣例輸入

2

0 1 0 1

樣例輸出

1

資料範圍

30%的資料N≤9；

60%的資料N≤1000；

100%的資料N≤200,000。

Analysis

樹狀數組–>如果資料範圍過大的話就需要離散化，但總的來說還是很好寫的

歸并排序–>懶得寫……

這種類型的題一定要get到，隻能允許相鄰的兩個點交換，就可以逆序對了

注意不可以在原數組上求逆序對，因為1 0 1 0和0 1 0 1其實是一緻的

而且我們有點類似貪心，是保證在前面的數不會被交換到後面去

最後注意一點：要開long long（手動算一下極端情況的逆序對個數： n ∗ ( n + 1 ) 2 \frac{n*(n+1)}{2} 2n∗(n+1)​)

Code

#include<bits/stdc++.h>
#define in read()
#define N 300000
#define ll long long 
using namespace std;
inline int read(){
	char ch;int f=1,res=0;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9') {
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return f==1?res:-res;
}
int n,id[N],cnt=0;
ll t[N];
inline ll lowbit(int x){return x&(-x);}
inline void insert(int pos){
	while(pos<=n){
		t[pos]++;
		pos+=lowbit(pos);
	}
}
inline ll query(int pos){
	ll ans=0;
	while(pos){
		ans+=t[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
int main(){
	n=in;
	int i,j;
	ll ans=0;
	for(i=1;i<=2*n;++i){
		j=in;
		if(!id[j])	id[j]=++cnt;
		insert(id[j]);
		ans+=i-query(id[j]);
	}
	cout<<ans;
	return 0;
}