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:

X Y: Swap (ax, ay)
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("%lldn",tree.queryRange(n,l,r,k));
        }
    }
}

HackerEarth Permutations problem solution.

Leave a Reply