程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3224 Tyvj 1728 普通平衡樹

BZOJ 3224 Tyvj 1728 普通平衡樹

編輯：C++入門知識

Splay入門題。。。斷斷續續寫了幾天。。。。

自己寫的常數好大。。。。。

3224: Tyvj 1728 普通平衡樹

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 862 Solved: 351
[Submit][Status]

Description

您需要寫一種數據結構（可參考題目標題），來維護一些數，其中需要提供以下操作：
1. 插入x數
2. 刪除x數(若有多個相同的數，因只刪除一個)
3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)
4. 查詢排名為x的數
5. 求x的前驅(前驅定義為小於x，且最大的數)
6. 求x的後繼(後繼定義為大於x，且最小的數)

Input

第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序號(1<=opt<=6)

Output

對於操作3,4,5,6每行輸出一個數，表示對應答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

Source

平衡樹

[Submit][Status]

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define Key_value (ch[ch[root][1]][0])

const int maxn=110100;
const int INF=0x3f3f3f3f;

int pre[maxn],ch[maxn][2],key[maxn],s[maxn];
int root,tot1;
map nct;

/************debug*********************/
void showit(int x)
{
    if(x)
    {
        showit(ch[x][0]);
        cout<<"節點："<0)
    {
        Splay(r,0);
        push_up(r);
    }
    else if(nct[x]<=0)
    {
        Splay(r,0);
        nct.erase(x);
        int rt=Find_Max(ch[root][0]);
        if(rt)
        {
            Splay(rt,root);
            pre[rt]=pre[root];
            ch[0][ch[0][1]==root]=rt;
            pre[ch[root][1]]=rt;
            ch[rt][1]=ch[root][1];
            root=rt;
        }
        else
        {
            if(ch[root][1])
            {
                pre[ch[root][1]]=0;
                ch[0][ch[0][1]==root]=ch[root][1];
                root=ch[root][1];
            }
            else init();
        }
        push_up(root);
    }
}

int get_rank(int x)
{
    int r=root,temp=0;

    while(ch[r][key[r]<=x])
    {
        if(key[r]==x) break;
        if(key[r]<=x) temp+=s[r]-s[ch[r][1]];
        r=ch[r][key[r]<=x];
    }
    return s[ch[r][0]]+1+temp;
}

int get_pre(int x)
{
    int ret=-INF;
    int r=root;
    while(r)
    {
        if(key[r]x)
        {
            ret=min(ret,key[r]);
            r=ch[r][0];
        }
        else r=ch[r][1];
    }
    return ret;
}

int get_kth(int x)
{
    int r=root;
    while(true)
    {
        int left=s[ch[r][0]],right=s[ch[r][0]]+nct[key[r]]+1;

        if(x>left&&x=right)
        {
            r=ch[r][1];
            x-=right-1;
        }
    }
}

int main()
{
    int T_T;
while(scanf("%d",&T_T)!=EOF)
{
    init();
    int a,b;
    for(int i=0;i