Merge tree (SPOJ MKTHNUM)

#include <iostream>
#include <vector>
#include <cstdio>
#define INF 1e9
#define For(i,x,n) for(int i=x; i<n; i++)
using namespace std;

struct ura{
    int x, y;
};

const int maxN = 1e5;
const int maxMagic = (1<<17);
int N, M, magic;
int input[maxN+10];
ura minmaxst[maxMagic * 2];
vector<int> ST[maxMagic * 2];

vector<int> MERGE(vector<int> A, vector<int> B){
    if(A.empty()) return B;
    if(B.empty()) return A;

    vector<int> ans;
    for(int i=0, j=0;;){
        if(i==A.size()){
            while(j<B.size())
                ans.push_back(B[j++]);
            break;
        }
        if(j==B.size()){
            while(i<A.size())
                ans.push_back(A[i++]);
            break;
        }
        if(A[i]<B[j]) ans.push_back(A[i++]);
        else ans.push_back(B[j++]);
    }
    return ans;
}

void build(int index, int s, int e){
    if(s>e) return;
    if(s==e){
        ST[index].push_back(input[s]);
        return;
    }

    build(index*2, s, (s+e)/2);
    build(index*2+1, 1+(s+e)/2, e);
    ST[index] = MERGE(ST[index*2], ST[index*2+1]);
}

void buildminmax(int index, int s, int e){
    if(s>e) return;
    if(s==e){
        minmaxst[index] = {input[s], input[s]};
        return;
    }

    buildminmax(index*2, s, (s+e)/2);
    buildminmax(index*2+1, 1+(s+e)/2, e);
    minmaxst[index] = { min(minmaxst[index*2].x, minmaxst[index*2+1].x),
                        max(minmaxst[index*2].y, minmaxst[index*2+1].y) };
}

ura queryminmax(int index, int s, int e, int qs, int qe){
    if(s>e || s>qe || e<qs) return {INF, -INF};
    if(s>=qs && e<=qe) return minmaxst[index];

    ura a = queryminmax(index*2, s, (s+e)/2, qs, qe);
    ura b = queryminmax(index*2+1, 1+(s+e)/2, e, qs, qe);
    return { min(a.x, b.x), max(a.y, b.y) };
}

int query(int index, int s, int e, int qs, int qe, int v){
    if(s>e || s>qe || e<qs) return 0;
    if(s>=qs && e<=qe)
        return lower_bound(ST[index].begin(), ST[index].end(), v) - ST[index].begin();

    return query(index*2, s, (s+e)/2, qs, qe, v) + query(index*2+1, 1+(s+e)/2, e, qs, qe, v);
}

int main()
{
    freopen("tests.in", "r", stdin);
    cin >> N >> M;
    For(i,0,N)
        cin >> input[i];
    for(magic=1; magic<N; magic<<=1);
    build(1,0,N-1);
    buildminmax(1,0,N-1);

    int a, b, k, l, r, e, z;
    ura aux;
    For(i,0,M){
        cin >> a >> b >> k;
        /// binary
        aux = queryminmax(1, 0, N-1, a-1, b-1);
        l = aux.x;
        r = aux.y;
        while(l<=r){
            e = (l+r)/2;
            z = query(1, 0, N-1, a-1, b-1, e);
            if( z > k-1 ) r=e-1;
            else if( z < k-1 ) l=e+1;
            else {
                cout << e << endl;
                break;
            }
        }
    }

    return 0;
}