optimizing selection sort with segment tree (1) 썸네일형 리스트형 선택 정렬의 개선 데추주를 위해 선택 정렬을 짜는데 무언가 익숙함이 느껴졌다. 어 이거... RMQ? RMQ는 세그먼트 트리를 이용하면 각 쿼리를 $O(logN)$에 구할 수 있음이 잘 알려져 있고, 선택 정렬을 시행할 때 필요한 쿼리의 수는 $N$번이다. 세그먼트 트리를 전처리하는 데에도 $O(NlogN)$이 필요하므로, 최종 시간복잡도 $O(NlogN)$에 배열을 정렬할 수 있다. BOJ 2751에 제출해보니 메모리와 시간 면에서 그다지 효율적이지는 않아도 나름 선전하는 모습을 보여줬다. #include using namespace std; #define nm (nl+nr>>1) typedef pair pii; const int N = 1e6+1; int n,a[N]; pii tree[4*N]; void init(in.. 이전 1 다음
