自动搬运

查看原文

来自洛谷，原作者为

	归褯雾嵊 **

搬运于2025-08-24 21:36:35，当前版本为作者最后更新于2018-09-14 10:54:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：开始给出m个宝石，她它们有各自的价值，然后会有好多询，或后者添加宝石操作，添加宝石就是把新宝石加入宝石堆里，询问的话是找价值第n大的宝石。

我一看这题就想到了一个叫做平衡树的东西，平衡树是二叉搜索树和堆合并构成的新数据结构，所以它的名字取了Tree和Heap各一半，叫做Treap，非常好用，而且这道题并不需要打整颗平衡树，只需要插入宝石到数中，在rank就行了

这个就是一个平衡树。不会的话就顺便去这里：(https://blog.csdn.net/qq_21120027/article/details/51713248) 学一个新的数据结构吧。。。

/*
ID:wang1441
LANG: C++
TASK:
*/
#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    int x=0;
    char ch=getchar();
    char c=ch;
    while(ch>'9'||ch<'0')c=ch,ch=getchar();
    while(ch<='9'&&ch>= '0')x=x*10+ch-'0',ch=getchar();
    if(c=='-')x=x*-1;
    return x;
}
//const int maxn=,maxm=;
struct node{
	node *wudi[2];
	int r,v,s;
	int cmp(int x)const
	{
		return x>v?0:1;
	}
	void maintain(){
		s=wudi[0]->s+wudi[1]->s+1;
	}
}*null,*root;

int a[100010];
int n,m;
int q,c;

void wwwwww(node * &o,int d)
{
	node * k=o->wudi[d^1];
	o->wudi[d^1]=k->wudi[d];
	o->maintain();
	k->maintain();
	k->wudi[d]=o;
	o=k;
}

void eeeeee(node * &o,int x)
{
	if(o==null){
		o=new node();
		o->wudi[0]=o->wudi[1]=null;
		o->v=x;
		o->r=rand();
		o->maintain();
	}
	else{
		int d=o->cmp(x);
		eeeeee(o->wudi[d],x);
		if(o->wudi[d]->r>o->r)
		    wwwwww(o,d^1);
		o->maintain();
	}
}

void tttttttttt()
{
	null=new node();
	null->s=0;
	root=null; 
}


void rrrrrrrrrrr(node * o,int x)
{
	if(o==null)
	    return ;
	int d=o->wudi[0]->s;
	if(x==d+1){
		printf("%d\n",o->v);
		return ;
	}
	if(x<d+1)
	    rrrrrrrrrrr(o->wudi[0],x);
	else
	    rrrrrrrrrrr(o->wudi[1],x-d-1);
}

int main()
{
    //freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	tttttttttt();
	m=read();
	q=read();
	srand(time(NULL));
	for(register int i=1;i<=m;i++){
		a[i]=read();
		eeeeee(root,a[i]);
	}
	for(register int i=1;i<=q;i++){
		c=read();
		n=read();
		if(c==1){
			rrrrrrrrrrr(root,n);
		}
		if(c==2){
			eeeeee(root,n);
		}
	}
}