程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 3043-迷之容器（Treap求第k小數）

SDUT 3043-迷之容器（Treap求第k小數）

編輯：C++入門知識

SDUT 3043-迷之容器（Treap求第k小數）

動態詢問第k小，只有插入和查詢兩種操作，第一發平衡樹。。紀念（sad 不全，沒有刪除操作，本題沒要求嘛）。主要是不會離散化用線段樹不會寫。。拼死敲了兩天Treap

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define maxn 1005
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1<<40+10
#define pp pair
#define ull unsigned long long
using namespace std;
int n;
struct node{
	node *ch[2];
	int r,v,s;
	node (){}
	node (int v){ch[0]=NULL;ch[1]=NULL;r=rand();this->v=v;s=1;}
	bool operator <(const node& c)const{
		return rs;
		if(ch[1]!=NULL)s+=ch[1]->s;
	}
};
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 insert(node* &o,int x)
{
	if(o==NULL) o=new node(x);
	else{
		int d=o->cmp(x);
		insert(o->ch[d],x);
		if(o->ch[d]->r>o->r)rotate(o,d^1);
	}
	o->maintain();
}
bool Find(node* o,int x)
{
	while(o!=NULL)
	{
		int d=o->cmp(x);
		if(d==-1)return 1;
		else o=o->ch[d];
	}
	return 0;
}
int find_kth(node* o,int k)
{
	if(o==NULL||k>o->s)return -1;
	int s=(o->ch[0]==NULL?0:o->ch[0]->s);
	if(k==s+1)return o->v;
	else if(k<=s) return find_kth(o->ch[0],k);
	else return find_kth(o->ch[1],k-s-1);
}
void solve()
{
	node *root=NULL;
	char op[2];int x;
	while(n--)
	{
		scanf(%s %d,op,&x);
		if(op[0]=='P')
		{
			if(Find(root,x))continue;
			insert(root,x);
		}
		else
			printf(%d
,find_kth(root,x));
	}
}
int main()
{
	while(~scanf(%d,&n))
		solve();
	return 0;
}