HackerEarth Permutations problem solution

1. X Y: Swap (ax, ay) 
2. L R K: Print MexK (aL,….,aR) 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int LOG = 18;
const int MAXSz = MAXN * LOG * LOG;

int A[MAXN];
queue<int> q;
int Size[MAXSz];
int Child[MAXSz][2];

bool Check(int x, int b) {return (x>>b)&1;}
void Initialize() {for(int i=0; i<MAXSz; i++) q.push(i);}
int CreateNode(){
    assert(q.size() >= 1);
    int x = q.front(); q.pop();
    Child[x][0] = Child[x][1] = -1;
    Size[x] = 0; return x;
}
void FreeNode(int node) {q.push(node); return;}
int Sz(int node) {return node == -1 ? 0 : Size[node];}

void Insert(int root, int n){
    int Cur = root;
    for(int i = LOG-1; i>=0; i--){
        bool ID = Check(n,i);
        if(Child[Cur][ID] == -1) Child[Cur][ID] = CreateNode();
        Cur = Child[Cur][ID];
        Size[Cur]++;
    }
}

void Delete(int root, int n){
    int Cur = root;
    int Prev = -1;

    for(int i = LOG-1; i>=0; i--){
        bool ID = Check(n,i);
        assert(Child[Cur][ID] != -1);

        Prev = Cur;
        Cur = Child[Cur][ID];
        Size[Cur]--;
        if(Size[Cur] == 0) FreeNode(Cur), Child[Prev][ID] = -1;
    }
}

struct SegmentTree{
    #define Left (node*2)
    #define Right (node*2+1)
    #define mid ((lo+hi)/2)

    int root[MAXN*5];
    vector<int> Qnode;

    void build(int node, int lo, int hi){
        root[node] = CreateNode();
        for(int x = lo; x <= hi; x++) Insert(root[node], A[x]);
        if (lo == hi) return;
        build(Left,lo,mid);
        build(Right,mid+1,hi);
    }

    void update(int node, int lo, int hi, int i, int val, bool Type){
        if(lo>hi) return;
        else if(lo>i || hi<i) return;

        if(Type) Insert(root[node],val);
        else Delete(root[node],val);
        if(lo == hi) return;

        update(Left,lo,mid,i,val,Type);
        update(Right,mid+1,hi,i,val,Type);
    }

    void splitRange(int node, int lo, int hi, int i, int j){
        if(lo>hi) return;
        else if(lo>j || hi<i) return;
        if(lo>=i && hi <= j) {Qnode.push_back(root[node]); return;}

        splitRange(Left,lo,mid,i,j);
        splitRange(Right,mid+1,hi,i,j);
    }

    int queryRange(int n, int i, int j, int k){
        Qnode.clear();
        splitRange(1,1,n,i,j);

        int Ans = 0;
        for(int i=LOG-1; i>=0; i--){
            int Total = 1<<i;
            vector <int> New;
            int Present, Missing;

            Present = 0;
            for(auto root : Qnode) Present += Sz(Child[root][0]);
            Missing = Total - Present;

            if(Missing >= k){
                for(int root : Qnode){
                    if(Child[root][0] != -1){
                        New.push_back(Child[root][0]);
                    }
                }
                Qnode = New;
            }
            else{
                Ans |= (1<<i);
                k -= Missing;
                for(int root : Qnode){
                    if(Child[root][1] != -1){
                        New.push_back(Child[root][1]);
                    }
                }
                Qnode = New;
            }
        }
        assert(k == 1);
        return Ans;
    }
};

SegmentTree tree;

int main(){
    Initialize();

    int n;
    scanf("%d",&n);
    assert(1 <= n && n <= 100000);

    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        assert(0 <= A[i] && A[i] < n);
    }

    tree.build(1,1,n);

    int q;
    scanf("%d",&q);
    assert(1 <= q && q <= 100000);

    for(int i=1;i<=q;i++){
        int tp;
        scanf("%d",&tp);
        assert(1 <= tp && tp <= 2);

        if(tp == 1){
            int l,r;
            scanf("%d %d",&l,&r);
            assert(1 <= l && l <= r && r <= n);

            tree.update(1,1,n,l,A[l],0);
            tree.update(1,1,n,r,A[r],0);
            swap(A[l],A[r]);
            tree.update(1,1,n,l,A[l],1);
            tree.update(1,1,n,r,A[r],1);
        }
        else{
            int l,r,k;
            scanf("%d %d %d",&l,&r,&k);
            assert(1 <= l && l <= r && r <= n);
            assert(1 <= k && k <= 100000);

            printf("%lldn",tree.queryRange(n,l,r,k));
        }
    }
}