Tag Archives: Treap

FZU 2100(排队-Treap维护队列最大值)

Posted on by
 Problem 2100 排队

Accept: 16    Submit: 160
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一些人在排队买车票，假设每个人都有不同的买票紧急程度，如果某个人的紧急程度比排在他前一个的人的紧急程度更大，则这个人可以和前一个人调换位置，并且假设每个人都有一个耐心值，若某人的耐心值为x，则他最多可以向前调换x次，当然前提是他之前x个人的紧急程度都比他小，若遇到前面一个人紧急程度比他大的他将停止往前调换。现假设有N个人，按顺序一个个进入队列，并且每进去一个人立即按照紧急程度和其耐心值向前进行调换，调换停止后下一个人才进入队列。给出这N个人的紧急程度和耐心值，问最终的排队情况。

Input

第一行输入一个整数T，表示数据组数。接下来T组数据，对于每组数据，第一行输入一个整数n (1<=n<=10^5)，接下来第2到n+1行每行输入两个整数a[i],c[i] (1<=a[i]<=n,0<=c[i]<=n)，分别表示第i个人的紧急程度在n个人种排第几及其耐心值，a[i]越大表示紧急程度越大。

Output

对于每组数据，请输出一行n个数，以一个空格隔开，表示最终队列的排队情况，第i个数表示最终排在第i个位置的人是第几个进入队列的。

Sample Input

152 31 44 33 15 2

Sample Output

3 1 5 4 2

Source

FOJ有奖月赛-2012年11月

这题因为把转移中的maxv打成v而Wa了一天（一天啊！）
言归正传，这题是要维护平衡树子树最大值，Treap的rotate是参考刘汝佳的写法。
就是insert时要根据左右子树的s(size)和maxv比大小

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
int t,n;
struct node
{
	int v,r,s,maxv,i;
	node *ch[2];
	node(int _v,int _i):s(1),r(rand()),v(_v),maxv(_v),i(_i){ch[0]=ch[1]=NULL;}
	bool operator<(const node &b){return r<b.r;}
	void maintain()
	{
		s=1;maxv=v;
		if (ch[0]!=NULL) {s+=ch[0]->s;maxv=max(maxv,ch[0]->maxv);}
		if (ch[1]!=NULL) {s+=ch[1]->s;maxv=max(maxv,ch[1]->maxv);}
	}
}*root=NULL;
void rotate(node *&o,int d)
{
	node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
	o->maintain();k->maintain();o=k;
}
void del(node *&o)
{
	if (o==NULL) return;
	del(o->ch[0]);
	del(o->ch[1]);
	delete o;
	o=NULL;
}
bool flag=1;
void print(node *&o)
{
	if (o->ch[0]!=NULL) print(o->ch[0]);
	if (flag) printf(" ");else flag=1;
	printf("%d",o->i);
	if (o->ch[1]!=NULL) print(o->ch[1]);
}
void insert(node *&o,int x,int k,int i)
{
	if (o==NULL){o=new node(x,i);return;	}
	int d;
	if (o->ch[1]==NULL)
	{
		if (k&&o->v<x) d=0;else d=1;
	}
	else if (o->ch[1]->s>=k||o->ch[1]->maxv>x||o->v>x) d=1;
	else d=0;
	if (d==0)
	{
		if (o->ch[1]!=NULL) k-=o->ch[1]->s;
		k--;
	}
	insert(o->ch[d],x,k,i);o->maintain();
	if (o->ch[d]<o) rotate(o,d^1);o->maintain();
}
int main()
{
//	freopen("fzu2100.in","r",stdin);
//	freopen("fzu2100.out","w",stdout);
	scanf("%d",&t);
	while (t--)
	{
		del(root);root=NULL;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			insert(root,x,y,i);
		}
		flag=0;print(root);printf("n");
	}
	return 0;
}

POJ 1442(Treap)

Posted on by
Language:
Black Box
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 5156   Accepted: 2085

Description

Black Box 代表数据库。（开始为空）
有2种操作
ADD (x): 向库添加一个x; 
GET: 第i次执行时输出数列中第i大的数. 

Example 1 

N Transaction i Black Box contents after transaction Answer

      (elements 升序排列)

1 ADD(3)      0 3

2 GET         1 3                                    3

3 ADD(1)      1 1, 3

4 GET         2 1, 3                                 3

5 ADD(-4)     2 -4, 1, 3

6 ADD(2)      2 -4, 1, 2, 3

7 ADD(8)      2 -4, 1, 2, 3, 8

8 ADD(-1000)  2 -1000, -4, 1, 2, 3, 8

9 GET         3 -1000, -4, 1, 2, 3, 8                1

10 GET        4 -1000, -4, 1, 2, 3, 8                2

11 ADD(2)     4 -1000, -4, 1, 2, 2, 3, 8

ADD 和 GET 操作数不超过 30000 . 

操作描述如下：
1. A(1), A(2), ..., A(M): Add 序列，|x|≤2 000 000 000 , M <= 30000. 样例中 A=(3, 1, -4, 2, 8, -1000, 2). 

2. u(1), u(2), ..., u(N):GET的询问时间，第i个GET将在第u(i)读完后执行.样例中 u=(1, 2, 6, 6). 

Input

第一行: M, N, 第二行序列A, 第三行序列u.

Output

第i行输出第i个GET的输出

Sample Input

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

Sample Output

3
3
1
2

Source

Northeastern Europe 1996


此题可用二叉搜索树解决。

二叉搜索树的建立：每拿到一个元素，比根小放在左根，比根大放在右根，否则放根上。

t.weight 表示结点上有几个数, t.key表示数的值 ,t.size表示以该点为根的树上有多少数

重点是左旋和右旋！

2个注意：注意把a的父亲结点改掉，注意把a,b的父亲结点改掉


下图转载自http://dongxicheng.org/structure/treap/



#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXM (30000+10)
#define MAXN (30000+10)
struct tree_node
{
	int key,fim,size,weight;
	tree_node *left,*right,*father;
	int l_size()
	{
		return (left==NULL)?0:(left->size);
	}
	int r_size()
	{
		return (right==NULL)?0:(right->size);
	}
	void count_size()
	{
		//size=(left==NULL)?0:(left->size)+(right==NULL)?0:(right->size)+weight;
		size=l_size()+r_size()+weight;
	}
	tree_node():key(0),fim(rand()),size(0),weight(0){left=right=father=NULL;}
	tree_node(int _key):key(_key),fim(rand()),size(1),weight(1){left=right=father=NULL;}
};
tree_node* newnode(int key)
{
	tree_node* p;
	p=new tree_node;
	*p=tree_node(key);
	return p;
}
struct Treep
{
	tree_node *root;
	Treep(){root=NULL;}
	void left_rotaue(tree_node *&a)
	{
		tree_node* b=a->right;
		a->right=b->left;if (a->right!=NULL) a->right->father=a;
		b->left=a;b->father=a->father;a->father=b;
		a->count_size();
		b->count_size();
		if (b->father)
		{
			if (b->father->left==a) b->father->left=b;
			else b->father->right=b;
		}
		a=b;
	}
	void right_rotaue(tree_node *&a)
	{
		tree_node* b=a->left;
		a->left=b->right;if (a->left!=NULL) a->left->father=a;
		b->right=a;
		b->father=a->father;
		a->father=b;
		a->count_size();
		b->count_size();
		if (b->father)
		{
			if (b->father->left==a) b->father->left=b;
			else b->father->right=b;
		}
		a=b;
	}
	void insert(int key)
	{
		if (root==NULL) {root=newnode(key);return;}
		tree_node *now=root;
		while (1)
		{
			now->size++;
			if (key==now->key) {now->weight++;break;}
			else if (key<now->key)
			{
				if (now->left==NULL) {now->left=newnode(key);now->left->father=now; now=now->left; break;}
				else now=now->left;
			}
			else
			{
				if (now->right==NULL) {now->right=newnode(key);now->right->father=now; now=now->right; break;}
				else now=now->right;
			}
		}
		for (;now!=root&&now->father->fim<now->fim;)
		{
			if (now->key<now->father->key) {now=now->father; right_rotaue(now);}
			else {now=now->father; left_rotaue(now); }
			if (now->father==NULL) root=now;
		}

	}
	int gets(int k)
	{
		tree_node* now=root;
		while (1)
		{
			if (now->l_size()>=k) {now=now->left;}
			else if (now->l_size()+now->weight>=k) return now->key;
			else {k-=now->l_size()+now->weight; now=now->right;}
		}
	}
	void print(tree_node *now)
	{
		if (now->left!=NULL)
		{
			cout<<"( ";
			print(now->left);
			cout<<" )";
		}
		cout<<" "<<now->key<<" ";
		if (now->right!=NULL)
		{
			cout<<"( ";
			print(now->right);
			cout<<" )";
		}


	}
}t;
int n,m,a[MAXN],u[MAXM];
int main()
{
//	freopen("poj1442.in","r",stdin);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=m;i++) cin>>u[i];
	for (int i=1,j=1;i<=n;i++)
	{
		t.insert(a[i]);//t.print(t.root);cout<<endl;
		while (j<=m&&i==u[j]) {cout<<t.gets(j)<<endl;j++;}
	}
	return 0;
}