Merge Sort Tree

머지 소트 트리란, 말 그대로 머지 소트의 과정을 그대로 저장하여 만들어논 트리이다.

예를 들어 최대 부분합 문제를 분할정복으로 푼 후, 그 과정을 세그먼트 트리로 옮겨 놓을 수 있듯이, 머지 소트가 일어나는 과정을 각각 하나의 노드로 만들어 저장하는 것이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, Q, A[MAXN+10];

vector<int> tree[4*MAXN+10];

void combine(vector<int> &a, vector<int> &b, vector<int> &c)
{
    int pa=0, pb=0;
    while(pa<a.size() || pb<b.size())
    {
        if(pa<a.size() && (pb==b.size() || a[pa]<b[pb])) c.push_back(a[pa++]);
        else c.push_back(b[pb++]);
    }
}

void init(int node, int tl, int tr)
{
    if(tl==tr)
    {
        tree[node].push_back(A[tl]);
        return;
    }
    int mid=tl+tr>>1;
    init(node*2, tl, mid);
    init(node*2+1, mid+1, tr);
    combine(tree[node*2], tree[node*2+1], tree[node]);
}

int query(int node, int tl, int tr, int l, int r, int k)
{
    if(r<tl || tr<l) return 0;
    if(l<=tl && tr<=r) return upper_bound(tree[node].begin(), tree[node].end(), k)-tree[node].begin();
    int mid=tl+tr>>1;
    return query(node*2, tl, mid, l, r, k)+query(node*2+1, mid+1, tr, l, r, k);
}

int kth(int l, int r, int k)
{
    int lo=-1e9-10, hi=1e9+10;
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(query(1, 1, N, l, r, mid)>=k) hi=mid;
        else lo=mid;
    }
    return hi;
}

int main()
{
    int i, j;
    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d", &A[i]);
    init(1, 1, N);
    while(Q--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        printf("%d\n", kth(a, b, c));
    }
}

 

두 노드를 합치는 combine 함수를 주의해서 구현하면 된다.

사실 이 과정은 STL 에 merge 함수가 이미 구현되어 있다.

 

중요한 것은 머지 소트 트리는 update 를 할 수 없고, update 를 빨리 하기 위해서는 각 정점이 vector 가 아닌, set이어야 한다는 점이다.

 

이 자료구조를 이용하여 K번째 수 문제를 풀 수 있고, 이진탐색 + $logN$ 개의 노드 + 파라마트릭 서치 => $O(Qlog^3{N})$ 안에 풀 수 있다.