merge sort tree

//kth_element
vector <int> tree[mx*4];

void init(int node, int b, int e){
    if (b == e) {
        tree[node].push_back(u[b-1].se);
        return;
    }
    int Left = node * 2;
    int Right = node * 2 + 1;
    int mid = (b + e) / 2;
    init(Left, b, mid);
    init(Right, mid + 1, e);
    tree[node].resize(tree[Right].size()+tree[Left].size());
    merge(tree[Left].begin(), tree[Left].end(), tree[Right].begin(), tree[Right].end(), tree[node].begin());
    //if(node==1) for(auto a: tree[node]) cout << a.se << " -> " << a.fi << endl;
}

int query(int node, int b, int e, int i, int j, int k){
    if(b==e) return tree[node][0];
    int Left = node * 2;
    int Right = node * 2 + 1;
    int mid = (b + e) / 2;
    int r = upper_bound(tree[Left].begin(), tree[Left].end(), j) - tree[Left].begin();
    int l = lower_bound(tree[Left].begin(), tree[Left].end(), i) - tree[Left].begin();
    int m = r - l;
    if(m >= k) return query(Left, b, mid, i, j, k);
    else return query(Right, mid+1, e, i, j, k-m);
}