백준 1517번: 버블 소트
16508 단어 Segment TreepscppSegment Tree
버블 소트
아이디어
문제 이름은 버블 소트지만 버블 소트 하면서 몇번 swap했나 세면 당연히 틀린다. N이 최대 500,000이므로 O(NlogN)에 풀어야 한다.
세그트리에 정렬 여부를 기록한다. 쿼리를 날리면 해당 구간에 정렬되지 않은 원소가 몇개인지 합을 구해서 알려준다.
작은 숫자부터(sort()하면 NlogN에 가능) 0 ~ 자기 인덱스에 정렬되지 않은 원소가 몇개인지 세서 정답에 더한다. 그리고 세그트리에 정렬했다고 업데이트해준다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> arr;
vector<int> tree;
int init(int start, int end, int node) {
if (start == end) return tree[node] = 1;
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
int query(int start, int end, int left, int right, int node) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
void update(int start, int end, int idx, int node, int value) {
if (start > idx || end < idx) return;
if (start == end) {
if (start == idx) tree[node] = value;
return;
}
update(start, (start+end)/2, idx, node*2, value);
update((start+end)/2+1, end, idx, node*2+1, value);
tree[node] = tree[node*2] + tree[node*2+1];
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
arr.push_back({x, i});
}
int h = (int)ceil(log2(N));
int size = (1<<h+1);
tree.resize(size);
init(0, N-1, 1);
sort(arr.begin(), arr.end());
long long ans = 0;
for (int i = 0; i < N; i++) {
int q = arr[i].second;
ans += query(0, N-1, 0, q, 1)-1;
update(0, N-1, q, 1, 0);
}
cout << ans;
return 0;
}
여담
세그트리 고수의 길.. 사실 합병정렬로 더 쉽게 풀 수 있다고 한다. 나중에 알아봐야겠다.
Author And Source
이 문제에 관하여(백준 1517번: 버블 소트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-1517번-버블-소트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)