hiho一下103周 平衡树·Treap

时间：2023-03-08 18:55:13

平衡树·Treap

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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

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

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

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

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

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

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

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

提示：Tree+Heap?

输入

第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个整数，表示针对询问的回答，保证一定有合法的解

样例输入
5

I 3

I 2

Q 3

I 5

Q 4
样例输出
3

3
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define inf 10000000000000

#define met(a,b) memset(a,b,sizeof a)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

typedef long long ll;

using namespace std;

const int N = 1e6+;

const int M = 4e5+;

struct is

{

    int l,r,v,si,rnd,w;//v 权值  rnd 堆的优先级   w为v的个数

} tree[N];

int n,sz,root,ans;

void update(int pos)

{

    tree[pos].si=tree[tree[pos].l].si+tree[tree[pos].r].si+tree[pos].w;

}

void lturn(int &pos)

{

    int t=tree[pos].r;

    tree[pos].r=tree[t].l;

    tree[t].l=pos;

    tree[t].si=tree[pos].si;

    update(pos);

    pos=t;

}

void rturn(int &pos)

{

    int t=tree[pos].l;

    tree[pos].l=tree[t].r;

    tree[t].r=pos;

    tree[t].si=tree[pos].si;

    update(pos);

    pos=t;

}

void pushin(int &k,int x)

{

    if(k==)

    {

        sz++;

        k=sz;

        tree[k].w=tree[k].si=;

        tree[k].rnd=rand();

        tree[k].v=x;

        return;

    }

    tree[k].si++;

    if(tree[k].v==x)tree[k].w++;

    else if(tree[k].v>x)

    {

        pushin(tree[k].l,x);

        if(tree[tree[k].l].rnd>tree[k].rnd)

            rturn(k);

    }

    else

    {

        pushin(tree[k].r,x);

        if(tree[tree[k].r].rnd>tree[k].rnd)

            lturn(k);

    }

}

void query(int pos,int x)

{

    if(pos==)return;

    if(tree[pos].v<=x)

    {

        ans=pos;

        query(tree[pos].r,x);

    }

    else query(tree[pos].l,x);

}

char ch[N];

int main()

{

    scanf("%d",&n);

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

    {

        int x;

        scanf("%s%d",ch,&x);

        if(ch[]=='I')

            pushin(root,x);

        else

            ans=,query(root,x),printf("%d\n",tree[ans].v);

    }

    return ;

}

相关文章