JOI 本選 2013-5 Bubble Sort

問題文 : バブルソート

解法 :

与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする.
すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.

愚直に数え上げを行えばこれはO(N^2) 時間で最大値が求まるが, セグメント木 & 尺取り法を用いてspeed-up をはかると, O(N log N) 時間で同等なことができる.
プログラム中にコメントを書いたのでそれを参考にしてください.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAX_N (100000)

using namespace std;

typedef long long lint;

lint bit[MAX_N + 1];

void add(int pos)
{
	for (; pos <= MAX_N; pos += pos & -pos)
		bit[pos] += 1;
}

lint sum(int pos)
{
	lint ret = 0;
	for (; pos; pos &= (pos - 1))
		ret += bit[pos];
	
	return (ret);
}

lint segAdd[1 << 18], segMax[1 << 18];

void add(int a, int b, lint x, int k = 0, int l = 0, int r = 1 << 17)
{
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		segAdd[k] += x;
		while (k){
			k = (k - 1) / 2;
			segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1],
							segMax[k * 2 + 2] + segAdd[k * 2 + 2]);
		}
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
}

int main()
{
	int N;
	int A[MAX_N];
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d", A + i);
	}
	vector<int> X(A, A + N);
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for (int i = 0; i < N; i++)
		A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin() + 1;
	
	lint ori = 0;
	
	for (int i = 0; i < N; i++){
		ori += i - sum(A[i]);
		add(A[i]);
	}
	
	lint ans = ori + 1 - (X.size() != N);
	
	int hi = 0;
	vector<int> uCand, dCand, other, uA;
	bool checked[MAX_N];
	
	memset(checked, 0, sizeof(checked));
	
	for (int i = 0; i < N; i++){
		if (A[i] > hi){
			hi = A[i];
			uCand.push_back(i);
			uA.push_back(A[i]);
			checked[i] = true;
		}
	}
	
	int lo = 100001;
	for (int i = N - 1; i >= 0; i--){
		if (A[i] < lo && !checked[i]){
			lo = A[i];
			dCand.push_back(i);
			checked[i] = true;
		}
	}
	reverse(dCand.begin(), dCand.end());
	
	vector<pair<int, int> > tmp;
	vector<int> sorted;
	for (int i = 0; i < N; i++){
		if (!checked[i]){
			other.push_back(i);
			tmp.push_back(make_pair(A[i], i));
		}
	}
	
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < tmp.size(); i++) sorted.push_back(tmp[i].second);
	
	int ohead = 0, otail = 0;
	for (int i = 0; i < dCand.size(); i++){
		//後ろを追い出す
		while (otail < sorted.size() && A[sorted[otail]] < A[dCand[i]]){
			int p = upper_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail]) - uCand.begin();
			add(p, q, -1);
			if (p && A[uCand[p - 1]] == A[sorted[otail]]) p--; //下の点と同じだったら交換したとき+2 じゃなくて +1
			add(p, q, -1);
			otail++;
		}
		
		//前を追加
		while (ohead < other.size() && other[ohead] < dCand[i]){
			int p = upper_bound(uA.begin(), uA.end(), A[other[ohead]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), other[ohead]) - uCand.begin();
			add(p, q, +1);
			if (p && A[uCand[p - 1]] == A[other[ohead]]) p--; //下の点と同じだったら交換したとき+2 じゃなくて +1
			add(p, q, +1);
			ohead++;
		}
		
		//重複してる点は, 交換したとき (長方形の中の点) * 2 にはなり得ない. +2 じゃなくて +1.
		int it = 0;
		while (otail + it < sorted.size() && A[sorted[otail + it]] == A[dCand[i]]){
			int p = lower_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();	// 同じ点は申し訳ないがNG
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail + it++]) - uCand.begin();
			add(p, q, -1);
		}
		
		int p = upper_bound(uA.begin(), uA.end(), A[dCand[i]]) - uA.begin();
		int q = upper_bound(uCand.begin(), uCand.end(), dCand[i]) - uCand.begin();
		//答えを更新
		if (p < q)
			ans = min(ans, ori - 1 - (segMax[0] + segAdd[0]));
		
		//後ろを追い出す (迫真)
		while (otail < sorted.size() && A[sorted[otail]] == A[dCand[i]]){
			int p = upper_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail++]) - uCand.begin();
			add(p, q, -1); //上で1 回引いているので.
		}
	}
	printf("%lld\n", ans);
	
	return (0);
}