BOJ 15757 - Out of sorts (세그 트리)

https://www.acmicpc.net/problem/15757

..

 

<문제설명>

일반적인 버블소트는 한 라운드당 한번씩 어떤 원소를 오른쪽으로 최대한 밀어준다.

 

문제에서의 소트는 추가로 어떤 원소를 최대한 왼쪽으로 밀어준다.

 

숫자배열이 주어질때, 배열이 정렬되려면 최소 몇번의 라운드가 필요한지 구하라

 

<풀이>

사이트 solution 풀이

 

Input array A:   1 8 5  |  3 2

Sorted version: 1 2 3  |  5 8

                          i    i+1

 

위처럼 구간을 둘로 나누는 선을 생각해서, 선 왼쪽의 sorted에 포함되는 동시에 선 오른쪽의 원래 배열에 포함되는 최대 원소 수를 구해주면 된다.

 

숫자는 여러번 나올수있고 범위가 넓으므로 숫자의 index를 기준으로 파악해주면 된다.

 

const int MAX = 1e5 + 4;
const int SMAX = (1 << 18);

int n, seg[SMAX];
P a[MAX];
void update(int i){
	i += (SMAX / 2);
	seg[i]=1;
	while (i > 1) {
		i /= 2;
		seg[i] = seg[i * 2] + seg[i * 2 + 1];
	}
}
int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return val(s, e, node * 2, ns, mid) + val(s, e, node * 2 + 1, mid + 1, ne);
}
int val(int s, int e) {
	return val(s, e, 1, 0, SMAX / 2 - 1);
}

int main() {
	FAST;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a, a + n);

	int ans = 1;
	for (int i = 0; i < n-1; i++) {
		update(a[i].second);
		ans = max(ans, i + 1 - val(0,i));
	}
	cout << ans << '\n';
}