[Algorithm] Merge Sort Tree 구현

Merge Sort Tree는 Segment Tree의 한 종류로, 그 값이 구간의 정렬된 배열을 들고 있는 것이 특징이다. Merge Sort Tree의 구현 또한 Struct를 써서 깔끔하게 구현할 수 있다.

Merge Sort Tree를 사용해서 구현할 수 있는 연산은
(1) 특정 구간의 k번째 작은값/큰값 -> O(log^3 N)
=> query(root, s, e, t) : s, e 구간에서 t보다 작은 값의 개수라 하면,
한 query를 처리하는 데의 시간복잡도 : 타고 내려가는데에 logN & 내려간 구간에서 lower_bound : logN

이 query를 t에 대해 이분탐색해서 특정 구간의 k번째 작은값을 구할 수 있다. => logN
즉, O(log^3 N)에 특정 구간의 k번째 작은 값을 구할 수 있다.

#include<bits/stdc++.h>
#define range(x) x->begin(), x->end()
using namespace std;
struct Node
{
	Node *l, *r;
	int s,e;
	vector<long long> *v;

	Node(int s,int e) : l(NULL), r(NULL), s(s), e(e), v(NULL){}
	~Node(){if(l) delete l; if(r) delete r; if(v) delete v; }
} *root;

void init(Node *node, int* arr)
{
	if(node->s == node->e)
	{
	    node->v = new vector<long long>;
		node->v->push_back(arr[node->s]);
		return;
	}
	int mid = (node->s + node->e)/2;

	node->l = new Node(node->s, mid);
	init(node->l, arr);

	node->r = new Node(mid+1, node->e);
	init(node->r, arr);

    node->v = new vector<long long>(node->e - node->s + 1);
	merge(range(node->l->v),range(node->r->v), node->v->begin());
}

int query(Node *node, int a,int b, long long k) //[i, j]에서 k가 몇번째 수인가? (k보다 작은 수의 개수)
{
    if(a <= node->s and node->e <= b) return lower_bound(range(node->v), k) - node->v->begin();
    if(b < node->s or node->e < a) return 0;

    return query(node->l,a,b,k) + query(node->r,a,b,k);
}
int arr[(int)1e5+7];
int main()
{
    int n, Q; scanf("%d %d", &n,&Q);
    for(int i = 1; i <= n; i++) scanf("%d", arr + i);

    root = new Node(1,n);
    init(root, arr);

    while(Q--)
    {
        int i,j,k; scanf("%d %d %d", &i,&j,&k);

        long long t, f = -(1<<30);
        for(t = (long long)1 << 31; t; t>>=1)
            if(query(root, i,j,f + t) < k)
                f += t;
        printf("%lld\n", f);
    }
    delete root;
}