【HIHOCODER 1325】平衡树·Treap

描述

小Ho：小Hi，我发现我们以前讲过的两个数据结构特别相似。

小Hi：你说的是哪两个啊？

小Ho：就是二叉排序树和堆啊，你看这两种数据结构都是构造了一个二叉树，一个节点有一个父亲和两个儿子。如果用1..n的数组来存储的话，对于二叉树上的一个编号为k的节点，其父亲节点刚好是k/2。并且它的两个儿子节点分别为k2和k2+1，计算起来非常方便呢。

小Hi：没错，但是小Hi你知道有一种办法可以把堆和二叉搜索树合并起来，成为一个新的数据结构么？

小Ho：这我倒没想过。不过二叉搜索树满足左子树<根节点<右子树，而堆是满足根节点小于等于(或大于等于)左右儿子。这两种性质是冲突的啊？

小Hi：恩，你说的没错，这两种性质的确是冲突的。

小Ho：那你说的合并是怎么做到的？

小Hi：当然有办法了，其实它是这样的....

输入

第1行：1个正整数n，表示操作数量，10≤n≤100,000

第2..n+1行：每行1个字母c和1个整数k：

若c为'I'，表示插入一个数字k到树中，-1,000,000,000≤k≤1,000,000,000

若c为'Q'，表示询问树中不超过k的最大数字

输出

若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解

样例输入

样例输出

3

3

题解

官方讲解treap还是不错的

传送门

#include <queue>

#include <cstdio>

#include <complex>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 1000000000

#define PI acos(-1)

#define bug puts("here")

#define REP(i,x,n) for(int i=x;i<=n;i++)

#define DEP(i,n,x) for(int i=n;i>=x;i--)

#define mem(a,x) memset(a,x,sizeof(a))

typedef unsigned long long ull;

using namespace std;

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline void Out(int a){

    if(a<0) putchar('-'),a=-a;

    if(a>=10) Out(a/10);

    putchar(a%10+'0');

}

const int N=100000+5;

int size,root;

struct data{int l,r,v,rnd;}tr[N];

void rturn(int &k){

     int t=tr[k].l;

     tr[k].l=tr[t].r;

     tr[t].r=k;k=t;

}

void lturn(int &k){

     int t=tr[k].r;

     tr[k].r=tr[t].l;

     tr[t].l=k;k=t;

}

void insert(int &k,int x){

	if(k==0){

        size++;k=size;

        tr[k].v=x;tr[k].rnd=rand();

        return;

    }

	if(tr[k].v==x) return;

	else if(x<tr[k].v){

        insert(tr[k].l,x);

        if(tr[tr[k].l].rnd<tr[k].rnd) rturn(k);

    }else{

        insert(tr[k].r,x);

        if(tr[tr[k].r].rnd<tr[k].rnd) lturn(k);

    }

}

int t1;

void dfs1(int k,int x){

	if(!k) return;

	if(x>=tr[k].v){

        t1=tr[k].v;

        dfs1(tr[k].r,x);

    }

	else dfs1(tr[k].l,x);

}

int main(){

    root=size=0;

    int n=read();char op;

    for(int i=1;i<=n;i++){

        cin>>op;

        int x=read();

        if(op=='I') insert(root,x);

        else{

           dfs1(root,x);

           Out(t1);puts("");

        }

    }

    return 0;

}

巴特西

【HIHOCODER 1325】平衡树·Treap

描述

输入

输出

样例输入

样例输出

题解

最新文章

热门文章

巴特西

【HIHOCODER 1325】 平衡树·Treap

描述

输入

输出

样例输入

样例输出

题解

最新文章

热门文章

【HIHOCODER 1325】平衡树·Treap