程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved