程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2985 Treap平衡樹（求第k大的元素）

POJ 2985 Treap平衡樹（求第k大的元素）

編輯：C++入門知識

這題也可以用樹狀數組做，而且樹狀數組姿勢更加優美，代碼更加少，不過這個Treap樹就是求第K大元素的專家……所以速度比較快！

這個也是從那本紅書上拿的模板……自己找了資料百度了好久，才理解這個Treap基本的知識，要是自己寫真的得寫到什麼時候啊！！！

然後輸入的時候是寫n-k+1反著找的，就是這裡又浪費了好多時間debug，唉……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 440004
#define MN 1008
#define INF 100000007
#define eps 1e-7
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
struct Treap
{
    int root,treapCnt,key[MM],priority[MM],childs[MM][2],cnt[MM],size[MM];
    Treap()
    {
        root=0;
        treapCnt=1;
        priority[0]=INF;
        size[0]=0;
    }
    void update(int x)
    {
        size[x]=size[childs[x][0]]+cnt[x]+size[childs[x][1]];
    }
    void rotate(int &x,int t)
    {
        int y=childs[x][t];
        childs[x][t]=childs[y][1-t];
        childs[y][1-t]=x;
        update(x);
        update(y);
        x=y;
    }
    void _insert(int &x,int k)
    {
        if(x)
        {
            if(key[x]==k) cnt[x]++;
            else
            {
                int t=key[x]1) cnt[x]--;
            else
            {
                if(childs[x][0]==0&&childs[x][1]==0)
                {
                    x=0;
                    return ;
                }
                int t=priority[childs[x][0]]>priority[childs[x][1]];
                rotate(x,t);
                _erase(x,k);
            }
        }
        else _erase(childs[x][key[x]