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
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;
}
Would you please provide the solution approach to the solution with AVL tree?
ReplyDelete