【Treap模闆題】洛谷 P3369 【模闆】普通平衡樹

洛谷 P3369 【模闆】普通平衡樹

題目描述

您需要寫一種資料結構（可參考題目标題），來維護一些數，其中需要提供以下操作：

1. 插入x數
2. 删除x數(若有多個相同的數，因隻删除一個)
3. 查詢x數的排名(排名定義為比目前數小的數的個數+1。若有多個相同的數，因輸出最小的排名)
4. 查詢排名為x的數
5. 求x的前驅(前驅定義為小于x，且最大的數)
6. 求x的後繼(後繼定義為大于x，且最小的數)

輸入格式：

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

輸出格式：

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

說明

時空限制：1000ms,128M

1.n的資料範圍： n \leq 100000n≤100000

2.每個數的資料範圍： [-{10}^7, {10}^7][−107,107]

來源：Tyvj1728 原名：普通平衡樹

在此鳴謝

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,sz,resz,val,rd;
    //分别是左節點，右節點，目前節點為根節點的節點數量，目前節點重複的數的數量，優先值
}t[500005];

int root,ans,tot;

void update(int k) //更新維護 
{
    t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].resz;
}

void left_rotate(int &k)
{
    int y=t[k].r;
    t[k].r=t[y].l;
    t[y].l=k;
    t[y].sz=t[k].sz;
    update(k);
    k=y;
}

void right_rotate(int &k)
{
    int y=t[k].l;
    t[k].l=t[y].r;
    t[y].r=k;
    t[y].sz=t[k].sz;
    update(k);
    k=y;
}

void ins(int &k,int x)  //以下函數的調用中(int k)表示在根為k的子樹中
{
    if(k==0)//無節點時特判
    {
        k=++tot;
        t[k].val=x;
        t[k].sz=t[k].resz=1;
        t[k].rd=rand();
        return;
    }
    t[k].sz++;//每次向下找同時增加該節點1個節點數
    if(t[k].val==x) t[k].resz++; //如果已有，就在原有上加
    else if(x>t[k].val)  //插右邊
    {
        ins(t[k].r,x);
        if(t[t[k].r].rd<t[k].rd) left_rotate(k);
    }
    else //插左邊
    {
        ins(t[k].l,x);
        if(t[t[k].l].rd<t[k].rd) right_rotate(k);
    }
}

void del(int &k,int x)
{
    if(k==0) return;
    if(t[k].val==x)
    {
        if(t[k].resz>1)
        {
            t[k].resz--,t[k].sz--;
            return;
        }
        //如果左右兒子有為空的情況,将其變為其兒子節點
        if(t[k].l*t[k].r==0) k=t[k].l+t[k].r;
        //如果其左右兒子都有，選擇優先級較大的，保持以後的堆性質，同時将k節點下沉
        else if(t[t[k].l].rd<t[t[k].r].rd) right_rotate(k),del(k,x);
        else left_rotate(k),del(k,x);
    }
    else if(x>t[k].val)
    {
        --t[k].sz,del(t[k].r,x);
    }
    else  --t[k].sz,del(t[k].l,x);
}

int atrank(int k,int x) //尋找值為x的數的排名
{
    if(k==0) return 0;
    if(x==t[k].val) return t[t[k].l].sz+1;
    else if(x>t[k].val) return t[t[k].l].sz+t[k].resz+atrank(t[k].r,x);
    else return atrank(t[k].l,x);
}

int rerank(int k,int x) //尋找排名為x的數值
{
    if(k==0) return 0;
    if(x<=t[t[k].l].sz) return rerank(t[k].l,x);
    else if(x>t[t[k].l].sz+t[k].resz) return rerank(t[k].r,x-t[t[k].l].sz-t[k].resz);
    else return t[k].val;
}

void pre(int k,int x) //找字首
{
    if(k==0) return;
    if(x>t[k].val)  //因為是在找字首，是以隻有我在後面的時候，更新的字首至少是更優的
    {
        //找到了更優的解，就替換之
		//而且在其右子樹中不可能再有更優的了
		//故向其左子樹中找
        ans=k;
        pre(t[k].r,x);
    }
    else pre(t[k].l,x);
}

void nex(int k,int x) //找字尾
{
    if(k==0) return;
    if(x<t[k].val)  //因為是在找字尾，是以隻有我在前面的時候，更新的字尾才是更優的
    {
        ans=k;
        nex(t[k].l,x);
    }
    else nex(t[k].r,x);
}



int main()
{
    int n;
    scanf("%d",&n);
    tot=0;
    for(int i=1;i<=n;i++)
    {
        ans=0;
        int Q,x;
        scanf("%d%d",&Q,&x);
        if(Q==1) ins(root,x);
        if(Q==2) del(root,x);
        if(Q==3) printf("%d\n",atrank(root,x));
        if(Q==4) printf("%d\n",rerank(root,x));
        if(Q==5)
        {
            pre(root,x);
            printf("%d\n",t[ans].val);
        }
        if(Q==6)
        {
            nex(root,x);
            printf("%d\n",t[ans].val);
        }
    }
    return 0;
}