题解 P2343 【宝石管理系统】

归褯雾嵊 · 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);
        }
    }
}