SID-Search Insert Delete

Search Insert Delete

Given below c++14 code is for sid spoj or search insert delete spoj.

Hint:- I just uses unordered_multimap container and whatever is said in question I have implemented that.

Time:- 0.23 sec

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 03 October 2015 (Saturday) 08:52
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
void scanchar(char &c){
    register int x = gc();
    for(;(x < 65 || x > 97);x = gc());
    c = x;
}
int main(){
    
    int n , m , temp;
    scanint(n);
    scanint(m);
    unordered_multimap<int , int > save;
    for(int i = 1 ; i<= n ; i++){
        scanint(temp);
        save.insert(mp(temp , i));
    }
    int val;
    char type;
    int initial_size = n;
    while(m--){
        scanchar(type);
        if(type == 'S'){
            scanint(val);
            auto it = save.equal_range(val);
            if(it.first != save.end()){
                auto x = it.first;
                auto y = it.first;
                y++;
                while(y!= it.second){
                    x = y;
                    y++;
                }
                printf("%d\n" , x->second);
            } else{
                printf("NONE\n");
            }
        } else if(type == 'I'){
            scanint(val);
            initial_size++;
            save.insert(mp(val , initial_size));
            printf("%d\n",initial_size);
        } else {
            scanint(val);
            auto it = save.equal_range(val);
            if(it.first!= save.end()){
                auto x = it.first;
                auto y = it.first;
                y++;
                while(y!= it.second){
                    x = y;
                    y++;
                }
                printf("%d\n" , x->second);
                save.erase(x);
            } else{
                printf("NONE\n");
            }
        }
    }
    return 0;
} 

ORDERSET-Order statistic set

Order statistic set

Given below code is for ORDERSET spoj or Order statistics set spoj.

Explanation :- Here I have used Policy Based Data Structure of C++ ,  You can read about this Design , Using & Testing. And it support all basic STL functions and some extra of it owns.
Time :- 0.65 sec

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int ,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>pbd_set;
int main(){
    pbd_set s;
    int t;
    scanf("%d ",&t);
    while(t--){
        char typ;
        int n;
        scanf(" %c%d",&typ , &n);
        if(typ == 'I')
            s.insert(n);
        else if (typ == 'D')
            s.erase(n);
        else if (typ == 'K'){
            int ans;
            n--;
            if(s.find_by_order(n) != s.end()){
                ans = *s.find_by_order(n);
                printf("%d\n",ans);
            }
            else 
                printf("invalid\n");
        }
        else{
            int ans = s.order_of_key(n);
            printf("%d\n",ans);
        }
    }
    return 0;
}

My solution for ORDERSET spoj or Order statistic set spoj problem using BIT(Binary Index Tree)
Time:- 0.46 sec

#include <bits/stdc++.h>
using namespace std;
#define MAX 200005
#define pb push_back
int tree[200009], hash[200009], save[200009];
void update(int pos , int data){
    while(pos <= MAX){
        tree[pos]+= data;
        pos += (pos & (-pos));
    }
}
int read(int pos){
    int ans = 0;
    while(pos){
        ans += tree[pos];
        pos -= (pos & -pos);
    }
    return ans;
}
struct data{
    int pos , data , hash;
    char type;
};
data d[200009], query[200009];
bool cmp(const data &a , const data &b){
    return a.data == b.data ? a.pos < b.pos : a.data < b.data;
}
int b_search(int k){

    int low = 0 , high = 200000 , mid;
    while(low < high){
        mid = (low + high)>>1;
        if(read(mid) >= k)
            high = mid;
        else
            low = mid+1;
    }
    return low;
}
int main(){
    int q ;
    scanf("%d",&q);
    for(int i = 0 ; i < q ; i++){
        scanf(" %c%d",&d[i].type , &d[i].data);
        d[i].pos = i+1;
    }

    sort(d , d + q , cmp);
    
    int cnt = 1 , prev = d[0].data;
    d[0].hash = cnt;
    save[cnt]= d[0].data;
    for(int i = 1 ; i < q ; i++)
    {
        if(prev != d[i].data){
            prev = d[i].data;
            cnt++;
            d[i].hash = cnt;
            save[cnt] = d[i].data;
        }
        else
            d[i].hash = cnt;
    }

    
    for(int i = 0 ; i < q ; i++){
        query[d[i].pos] = d[i];
    }

    cnt = 0;
    for(int i = 1 ; i <= q ; i++){
        if(query[i].type == 'I'){
            if(!hash[query[i].hash]){
                cnt++;
                hash[query[i].hash] = 1;
                update(query[i].hash , 1);
            }
        }
        else if(query[i].type == 'D'){

            if(hash[query[i].hash]){
                cnt--;
                hash[query[i].hash] = 0;
                update(query[i].hash , -1);
            }
        }

        else if(query[i].type == 'K'){
            if(query[i].data > cnt)
                printf("invalid\n");
            else
                printf("%d\n",save[b_search(query[i].data)]);
        }
        else
            printf("%d\n",read(query[i].hash - 1));
    }
    return 0;
}

My solution for ORDERSET spoj or Order statistic set spoj using Height Balanced Tree(AVL Tree ) I copied AVL tree code from geeks for geeks . For learning AVL tree you can refer to geeks for geeks :- http://www.geeksforgeeks.org/avl-tree-set-2-deletion/
Time :- 0.67 sec

#include <bits/stdc++.h>
using namespace std;
class node{
public:
 int val , height , sum ;
 node * left , *right;
    node(){
        val = height = sum = 0;
        left = right = NULL;    
    }
};
int get_sum(node *x){
    
    if(x == NULL)
        return 0;
    return x->sum;
}
node *get_new_node(int key){

    node *temp = new node();
    temp->val =  key;
 temp->left = NULL;
 temp->right = NULL;
 temp->height = 1;
 temp->sum = 1;
    return temp;
}

bool find(int key , node *root){
 
 if(root == NULL)
  return false;
 if(key < root->val)
  return find(key , root->left);
 else if(key > root->val)
  return find(key , root->right);
 else
  return true;
}

int get_height(node *x){
 
 if(x==NULL)
  return 0;
 return x->height;
}

int get_diff(node *x){

    if(x == NULL)
        return 0;
    return get_height(x->left) - get_height(x->right);
}
node *left_rotate(node *x){
 
 node *y  = x->right;
 node *y_left = y->left;

 y->left = x;
 x->right = y_left;

 x->height = max(get_height(x->left) , get_height(x->right)) + 1;
    x->sum = get_sum(x->left) + get_sum(x->right) + 1;
    y->height = max(get_height(y->left) , get_height(y->right)) + 1;
    y->sum = get_sum(y->left) + get_sum(y->right) + 1;
    return y;
}

node *right_rotate(node *x){

    node *y = x->left;
    node *y_right = y->right;

    y->right = x;
    x->left = y_right;
    
    x->height = max(get_height(x->left) , get_height(x->right)) + 1;
    x->sum = get_sum(x->left) + get_sum(x->right) + 1;
    y->height = max(get_height(y->left) , get_height(y->right)) + 1;
    y->sum = get_sum(y->left) + get_sum(y->right) + 1;
    return y;
}
node *insert(node *root , int key){

    if(root == NULL)
        return get_new_node(key);

    if(key < root->val)
        root->left = insert(root->left , key);

    else
        root->right = insert(root->right , key);

    root->height = max(get_height(root->left) , get_height(root->right)) + 1;
    root->sum = get_sum(root->left) + get_sum(root->right) + 1;
    int diff ;
    if(root == NULL)
        diff = 0;
    else
        diff = get_height(root->left) - get_height(root->right);

    if(diff > 1 && key < root->left->val)
        return right_rotate(root);
    if(diff < -1 && key > root->right->val)
        return left_rotate(root);
    if(diff > 1 && key > root->left->val){
        root->left = left_rotate(root->left);
        return right_rotate(root);
    }
    if(diff < -1 && key < root->right->val){
        root->right = right_rotate(root->right);
        return left_rotate(root);    
    }
    
    return root;
}
node *del(node * root , int key){

    if(root == NULL)
        return root;
    
    if(key < root->val)
        root->left = del(root->left , key);
    else if(key > root->val)
        root->right = del(root->right , key);

    else{
        
        if(root->left == NULL || root->right == NULL){
            
            node *temp = root->left ? root->left : root->right;
            if(temp == NULL){
                
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;        
        }
        else{
            
            node *temp = root->right;
            while(temp->left != NULL)
                temp = temp->left;
            
            root->val = temp->val;

            root->right = del(root->right , temp->val);        
        }
    }
    
    if(root == NULL)
        return root;
    root->height = max(get_height(root->left) , get_height(root->right)) + 1;
    root->sum = get_sum(root->left) + get_sum(root->right) + 1;
    int diff = get_height(root->left) - get_height(root->right);
    
    if (diff > 1 && get_diff(root->left) >= 0)
        return right_rotate(root);
 
    if (diff > 1 && get_diff(root->left) < 0)
    {
        root->left =  left_rotate(root->left);
        return right_rotate(root);
    }
 
    if (diff < -1 && get_diff(root->right) <= 0)
        return left_rotate(root);
 
    if (diff < -1 && get_diff(root->right) > 0)
    {
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }
    return root;
}
int get_by_order(node *root , int key){

    if(root == NULL)
        return 0;
    int left_size = get_sum(root->left);
    if(left_size == key)
        return root->val;
    if(key < left_size)
        return get_by_order(root->left , key);
    else
        return get_by_order(root->right , key - left_size - 1);
}
int order_of_key(node *root , int key){

    if(root == NULL)
        return 0;

    if(key < root->val)
        return order_of_key(root->left , key);
    else if(key == root->val){
        if(root->left != NULL)
            return get_sum(root->left) + 1;
        else 
            return 1;
    }
    else
    {
        if(root->left != NULL )
            return get_sum(root->left) + 1 + order_of_key(root->right , key);
        else
            return 1 + order_of_key(root->right , key);
    }
}

int main(){
    
    int q;
    scanf("%d",&q);
    node *root = NULL;
    while(q--){

        char c ;
        int value;
        scanf(" %c%d",&c , &value);
        if(c=='I'){

            if(!find(value , root)){
                root = insert(root , value) ;
            }
        }
        else if(c == 'D'){
            root = del(root , value ) ;
        }
        else if(c == 'C'){
            int ans = order_of_key(root , value);
            if(find(value , root))
                printf("%d\n",ans - 1);
            else
                printf("%d\n",ans);
        }
        else
        {
            value--;
            if(root == NULL)
                printf("invalid\n");
            else if( root->sum <= value)
                printf("invalid\n");
            else
                printf("%d\n",get_by_order(root , value));
        }
    }
    return 0;
}