---
tags: algorithm
---

# 分治

把大問題分成小問提
再從小問題合併上來

**必要條件**:你要確保合併是正確的

digraph {
	"1~8" -> {"1~4", "5~8"}
	"1~4" -> {"1~2", "3~4"}
	"5~8" -> {"5~6", "7~8"}
	"1~2" -> {"1", "2"}
	"3~4" -> {"3", "4"}
	"5~6" -> {"5", "6"}
	"7~8" -> {"7", "8"}
}

## 分

digraph {
 "[3, 7, 4, 6,2 ,5, 9, 1]"
 "[3, 7, 4, 6,2 ,5, 9, 1]" -> {"[3, 7, 4, 6]", "[2 ,5, 9, 1]"}
 
 "[3, 7, 4, 6]" -> {"[3, 7]", "[4, 6]"}
 "[3, 7]" -> {"[3]", "[7]"}
 "[4, 6]" -> {"[4]", "[6]"}
 "[2 ,5, 9, 1]" -> {"[2, 5]", "[9, 1]"}
 "[2, 5]" -> {"[2]", "[5]"}
 "[9, 1]" -> {"[9]", "[1]"}
}

## 治

digraph{
	{"[3]" "[7]"} -> "[3, 7]"
	{"[4]" "[6]"} -> "[4, 6]"
	{"[3, 7]", "[4, 6]"} -> "[3, 4, 6, 7]"
	
	{"[2]", "[5]"} -> "[2, 5]"
	{"[9]", "[1]"} -> "[1, 9]"
	{"[2, 5]", "[1, 9]"} -> "[1, 2, 5, 9]"
	{"[3, 4, 6, 7]","[1, 2, 5, 9]"} -> "[1, 2, 3, 4, 5, 6, 7, 9]"
}

# merge sort

#define inf int(2e9)
//#define inf 10000000000000000000000LL 
void merge_sort(vector<int> &vc) {
	if( vc.size() == 1 ) return;
	const int sz = vc.size();
	int m = sz>>1;
	vector<int> vl( vc.begin(), vc.begin()+m ), vr( vc.begin()+m, vc.end() );
	merge_sort( vl ); merge_sort( vr );
	
	//merge( vl.begin(), vl.end(), vr.begin(), vr.end(), vc.begin() );	
	//v1 = vc[ 0~m-1 ]
	
	int l_pos = 0, r_pos = 0, vc_pos = 0;
	while( l_pos != int(vl.size()) && r_pos != int(vr.size()) ) {// vl.size()-1
		if( vl[ l_pos ] > vr[ r_pos ] ) vc[ vc_pos ] = vr[ r_pos ], r_pos++;
		else vc[ vc_pos ] = vl[ l_pos ], l_pos++;
		vc_pos++;
	}
	while( l_pos != int( vl.size() )) vc[ vc_pos ] = vl[ l_pos ], vc_pos++, l_pos++;
	while( r_pos != int( vr.size() )) vc[ vc_pos ] = vr[ r_pos ], vc_pos++, r_pos++;
	return;
}
int main () {
	int N; cin >> N;
	//2^k ,

	int sz = 1<<(__lg(N-1)+1); // 2 << __lg(vc.size()-1)

	// 1<<q => 2^q	
	
	//vc.size() = 4, 1<<(1+1)
	
	vector<int> vc(sz, inf);


	for( int i = 0; i < N; i++ ) {
		int a; cin >> a;
		vc.emplace_back(a);
	}


	merge_sort(vc);

	for( int i = 0; i < N; i++ ) cout << vc[i] << " \n"[i==N-1];
}

## [a132](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a132)

long long sum = 0LL;

void merge_sort( vector<int> &vc ) {
	if( vc.size() == 1 ) return;
	const int sz = vc.size();
	int m = sz>>1; //sz/2
	
	vector<int> vl( vc.begin(), vc.begin()+m ), vr( vc.begin()+m, vc.end() );
	merge_sort( vl ); merge_sort( vr );

	int l_pos = 0, r_pos = 0, vc_pos = 0;
	while( l_pos != int( vl.size() ) && r_pos != int( vr.size() ) ) {
		if( vl[ l_pos ] == vr[ r_pos ] ) {
			sum += r_pos;
			vc[ vc_pos ] = vl[ l_pos ];
		   	l_pos++;
		}
		else if( vl[ l_pos ] > vr[ r_pos ] ) vc[ vc_pos ] = vr[ r_pos ], r_pos++;
		else if( vl[ l_pos ] < vr[ r_pos ] ) {
			sum += r_pos;
			vc[ vc_pos ] = vl[ l_pos ];
			l_pos++;
		}
		vc_pos++;
	}

	while( r_pos != int( vr.size() ) ) vc[ vc_pos ] = vr[ r_pos ], r_pos++, vc_pos++;
	while( l_pos != int( vl.size() ) ) {
		sum += r_pos;
		vc[ vc_pos ] = vl[ l_pos ]; 
		l_pos++;
		vc_pos++;
	}
	return;
}
void solve() {
	sum = 0LL;
	int N; cin >> N;
	vector<int> vc(N);
	for( int i = 0; i < N; i++ ) cin >> vc[i]; // for(auot &i : vc) cin >> i;
	merge_sort( vc );

	cout << sum << '\n';
}
int main () {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while( T-- ) solve();
}

## [a139](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a139)

struct point {
	int x, y;
	int	org_pos, ans;

	point() {};
	point( int _x, int _y, int _org_pos ) : x(_x), y(_y), org_pos(_org_pos) {ans = 0;}
};

bool x_cmp( const point &a, const point &b ) {
	return (a.x == b.x ? a.y > b.y : a.x < b.x );
}

bool pos_cmp( const point &a, const point &b) {
	return a.org_pos < b.org_pos;
}

void merge_sort(vector<point> &vc) {
	if( vc.size() == 1 ) return;
	const int sz = vc.size();
	int m = sz>>1;//sz/2
	vector<point> vl( vc.begin(), vc.begin()+m), vr( vc.begin()+m, vc.end() );
	merge_sort( vl ); merge_sort( vr ); 

	int l_pos = 0, r_pos = 0, vc_pos = 0;
	while( l_pos != int( vl.size() ) && r_pos != int( vr.size() ) ) {
		if( vl[ l_pos ].y == vr[ r_pos ].y ) vc[ vc_pos ] = vr[ r_pos ], r_pos++;
		else if( vl[ l_pos ].y > vr[ r_pos ].y ) vc[ vc_pos ] = vr[ r_pos ], r_pos++;
		else {
			//cout << "1: " << vl[ l_pos ].org_pos << " " << r_pos << ' ' << vr.size() << endl;
			vl[ l_pos ].ans += int( vr.size() ) - r_pos;
			vc[ vc_pos ] = vl[ l_pos ];
			l_pos++;
		}

		vc_pos++;
	}

	while( r_pos != int( vr.size() ) )  vc[ vc_pos ] = vr[ r_pos ], r_pos++, vc_pos++;
	while( l_pos != int( vl.size() ) )  {
		//cout << "2: " << vl[ l_pos ].org_pos << " " << r_pos << ' ' << vr.size() << endl;
		vl[ l_pos ].ans += int( vr.size() ) - r_pos;
		vc[ vc_pos ] = vl[ l_pos ];
	   	l_pos++;
		vc_pos++;
	}	
	/*
	cout << "-----------------------\n";
	for( auto &i : vc ) {
		cout << i.x << ' ' << i.y << ' ' << i.org_pos << ' ' << i.ans << '\n';
	}
	cout << "----------------------\n";
	*/
	


	return;
}
void solve(int N) {
	vector<point> vc(N);
	for(int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		vc[i] = point( x, y, i );
	}
	
	sort( vc.begin(), vc.end(), x_cmp);	
	/*
	cout << "-----------------------\n";
	for( auto &i : vc ) {
		cout << i.x << ' ' << i.y << ' ' << i.org_pos << '\n';
	}
	cout << "----------------------\n";
	*/

	merge_sort(vc);

	sort( vc.begin(), vc.end(), pos_cmp );
	for( auto &i : vc ) {
		cout << i.ans << '\n';
	}
}