# HackerEarth Permutations problem solution

In this HackerEarth Permutations problem solution you are given a permutation A = {a1,a2,a3,...aN} of N integers from 0 to N - 1.

You are also given Q queries of the following two forms:
1. X Y: Swap (ax, ay)
2. L R K: Print MexK (aL,....,aR)
Here, MexK(aL,...,aR) = Kth smallest non-negative integer that is not available in the subarray (aL,...,aR).

You can answer the next query only when you answer the previous one. You must answer these queries online.

## HackerEarth Permutations problem solution.

`#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("%lld\n",tree.queryRange(n,l,r,k));        }    }}`