Pagini recente » Cod sursa (job #528304) | Cod sursa (job #1975357) | Cod sursa (job #1405900) | Cod sursa (job #2779795) | Cod sursa (job #2306268)
#include<bits/stdc++.h>
using namespace std;
struct Treap
{
int priority;
int key;
int weight;
Treap *left,*right;
Treap(int priority,int key,int weight,Treap *left,Treap *right)
{
this->priority=priority;
this->key=key;
this->weight=weight;
this->left=left;
this->right=right;
}
}*root,*nil;
void setup()
{
srand(time(0));
root=nil=new Treap(0,0,0,NULL,NULL);
}
inline int Rand()
{
return 1 + (((rand()%32768)<<15) + rand()%32768 + 1 );
}
void update_weight(Treap *node)
{
if(node==nil) node->weight=0;
else node->weight=1+node->left->weight+node->right->weight;
}
void rotright(Treap* &node)
{
Treap *w=node->left;
node->left=w->right;
w->right=node;
node=w;
}
void rotleft(Treap* &node)
{
Treap *w=node->right;
node->right=w->left;
w->left=node;
node=w;
}
void balance(Treap* &node)
{
if(root->priority<root->left->priority)
{
rotright(node);
update_weight(node->right);
update_weight(node);
}
else
if(root->priority<root->right->priority)
{
rotleft(node);
update_weight(node->left);
update_weight(node);
}
}
void insert_node(Treap* &node,int pos,int priority,int key)
{
if(node==nil)
{
node=new Treap(priority,key,1,nil,nil);
}
else
{
if(node->left->weight>=(pos-1)) insert_node(node->left,pos,priority,key);
else insert_node(node->right,pos-node->left->weight-1,priority,key);
balance(node);
update_weight(node);
}
}
void dfs(Treap *node)
{
if(node==nil) return;
update_weight(node);
dfs(node->left);
printf("%d\n",node->key);
dfs(node->right);
}
int n,x;
int main()
{
freopen("schi.in","r",stdin);
freopen("schi.out","w",stdout);
scanf("%d",&n);
setup();
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
insert_node(root,x,Rand(),i);
}
dfs(root);
return 0;
}