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;
}

KQUERY-K-query

K-query

Given below c++ code is for kquery spoj .

Here I have implemented it through BIT and offline query .First I have sorted data and query according to its K in descending order . Now for each K I calculate all the number which are greater then K and updated it to BIT , and for I and J I queried from tree .

#include <bits/stdc++.h>
using namespace std;
#define MAX 30001
int tree[30009];
void update(int pos){
    while(pos<=MAX){
        tree[pos]+=1;
        pos += (pos & -pos);
    }
}
int query(int pos){
    int result = 0;
    while(pos){
        result += tree[pos];
        pos -= (pos & -pos);
    }
    return result;
}
struct data{
    int value , pos;
};
struct query_data{
    int i , j , k , pos;
};
bool compare(const data &a , const data &b){
    return a.value > b.value;
}
bool cmp(const query_data &a , const query_data &b){
    return a.k > b.k;
}
int main(){
    int n;
    scanf("%d",&n);
    data arr[n+9];
    for(int i = 0 ; i < n ; i++)
        scanf("%d",&arr[i].value), arr[i].pos = i+1;
    sort(arr , arr+n , compare);
    int q_no;
    scanf("%d",&q_no);
    query_data q[q_no+9];
    for(int i = 0 ; i < q_no ; i++)
        scanf("%d%d%d",&q[i].i ,&q[i].j , &q[i].k) , q[i].pos = i;
    int result[q_no + 9];
    sort(q , q+q_no , cmp);
    int pos = 0;
    for(int i = 0 ; i<q_no ; i++){
        while(pos < n && arr[pos].value > q[i].k){
            update(arr[pos].pos);
            pos++;
        }
        result[q[i].pos] = query(q[i].j) - query(q[i].i - 1);
    }
    for(int i = 0 ; i < q_no ; i++)
        printf("%d\n",result[i]);
    return 0;
}

DCEPC206 - Its a Murder!

Its a Murder!

Given below code is for decpc206 spoj or its a murder spoj .

Hint : - > BIT 

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
#define MAX 100001
LL tree[100009];
LL read(int pos)
{
    LL res = 0;
    while(pos)
    {
        res += tree[pos];
        pos -= (pos & -pos);
    }
    return res;
}
void update(int pos , int val)
{
    while(pos<=MAX)
    {
        tree[pos] += val;
        pos +=(pos & -pos);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int arr[n+9] , hold[n+9] ;
        for(int i = 0; i < n ; i++){
            scanf("%d",&arr[i]);
            hold[i] = arr[i];
        }
        sort(arr,arr+n);
        for(int i = 0; i < n ; i++)
        {
            int pos = lower_bound(arr , arr + n , hold[i]) - arr;
            hold[i] = pos;
        }
        LL sum = 0;
        memset(tree, 0 , sizeof tree);
        for(int i = 0; i < n ; i++)
        {
            sum += read(hold[i]);
            update(hold[i] + 1 , arr[hold[i]]);
        }
        printf("%lld\n",sum);
    }
    return 0;
}

MSE06H - Japan

Japan

given below code is for mse06h spoj or japan spoj .

Hint :->use BIT .

#include <bits/stdc++.h>
using namespace std;
struct par
{
    int f,s;
};
int tree[1009];
long long read(int pos)
{
    long long count = 0;
    while(pos)
    {
        count += tree[pos];
        pos -= (pos & -pos);
    }
    return count;
}
void update(int pos ,int MAX)
{
    while(pos <= MAX)
    {
        tree[pos]+=1;
        pos += (pos & -pos);
    }
}
bool compare(const par &a ,const par &b)
{
    return a.f == b.f ? a.s < b.s : a.f < b.f;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int l  =1 ; l<=t ; l++)
    {
        int n , m ,k ,a,b ;
        scanf("%d%d%d",&n,&m,&k);
        par p[1000009];
        memset(tree,0,sizeof tree);
        for(int i = 0; i < k ; i++){
            scanf("%d%d",&a , &b);
            p[i].f = a;
            p[i].s = b;
        }
        sort(p,p+k,compare);
        long long  res = 0;
        for(int i = 0 ; i < k ; i++)
        {
            res += (read(m) - read(p[i].s));
            update(p[i].s , m);
        }
        printf("Test case %d: %lld\n",l,res);
    }
    return 0;
}

NICEDAY - The day of the competitors

The day of the competitors

Given Below c++ code is for NICEDAY spoj or the day of the competitiors spoj.

Hint :-> Binary Index Tree

(copied):

#include <bits/stdc++.h>
using namespace std;
int tree[100009];
void update(int pos,int val,int MAX)
{
    while(pos <= MAX)
    {
        tree[pos] = min(tree[pos] , val);
        pos += (pos & -pos);
    }
}
int read(int pos)
{
    int check = INT_MAX;
    while(pos)
    {
        check = min(tree[pos] , check);
        pos -= (pos & -pos);
    }
    return check;
}
struct data
{
    int first,second,third;
};
bool cmp(const data &a , const data &b)
{
    return a.first == b.first ? (a.second == b.second ? a.third < b.third : a.second < b.second ) : a.first < b.first;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        data arr[n+9];
        for(int i=0;i<n;i++)
            scanf("%d%d%d",&arr[i].first,&arr[i].second,&arr[i].third);
        sort(arr,arr+n,cmp);
        fill(tree,tree + n + 9 , INT_MAX);
        int res = 0;
        for(int i =0; i<n ; i++)
        {
            int curr = read(arr[i].second);
            if(curr > arr[i].third)
                res++;
            update(arr[i].second,arr[i].third,n+9);
        }
        printf("%d\n",res);
    }
    return 0;
}

YODANESS-Yodaness Level

Yodaness Level

Given Below code is for yodaness spoj or yodaness level spoj.

Hint :-> Its just simple problem on BIT for counting inversion count . (read bit from top coder)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void update(LL arr[],int pos,int val,int MAX)
{
    while(pos<=MAX)
    {
        arr[pos] += val;
        pos += (pos & -pos);
    }
}
LL read(LL arr[],int pos)
{
    LL sum = 0;
    while(pos)
    { 
        sum += arr[pos];
        pos -= (pos & -pos);
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        string s[n+9],temp;
        for(int i = 0;i < n;i++)
            cin>>s[i];
        int count = 1;
        map<string,int> mp;
        while(count<=n){
            cin>>temp;
            mp[temp] = count;
            count++;
        }
        int arr[n+9];
        count = 0;
        for(int i = 0;i<n;i++)
            arr[i] = mp[s[i]];
        LL tree[n+9];
        memset(tree,0,sizeof tree);
        LL total = 0;
        for(int i = n - 1 ; i >= 0 ; i--)
        {
            total += read(tree,arr[i]);
            update(tree,arr[i],1,n+9);
        }
        printf("%lld\n", total);
    }
    return 0;
}

MATSUM-Matrix Summation

Matrix Summation

Given below code is for MATSUM or matrix summation .

Hint :- Use 2-D Binary Index Tree (read from top coder tutorial.

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
LL tree[1050][1050];
void update(int x,int y,int val,int MAX)
{
    while(x<=MAX)
    {
        int ty = y;
        while(ty <= MAX)
        {
            tree[x][ty] += val;
            ty += (ty & -ty);
        }
        x += (x & -x);
    }
}
LL read(int x,int y)
{
    LL sum = 0;
    while( x )
    {
        int ty = y;
        while( ty )
        {
            sum += tree[x][ty];
            ty -= (ty & -ty);
        }
        x -= (x & -x);
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        memset(tree,0,sizeof tree);
        while(1)
        {
            char s[10];
            scanf("%s",s);
            if(s[1] == 'E'){
                int x,y,val;
                scanf(" %d%d%d",&x,&y,&val);
                LL p_val = read(x+1,y+1) + read(x,y) - read(x+1,y) - read(x,y+1);
                update(x+1,y+1,val - p_val,n+9);
            }
            else if(s[1] == 'U')
            {
                LL sum = 0;
                int x1,y1,x,y;
                scanf(" %d%d%d%d",&x,&y,&x1,&y1);
                sum = read(x1+1,y1+1) + read(x,y) - read(x,y1+1) - read(x1+1 , y);
                printf("%lld\n",sum);
            }
            else{
                //printf("\n");
                break;
            }
        }
        printf("\n");
    }
    return 0;
}