洛谷P3369 模板 普通平衡樹

2022-09-23 02:32:07 字數 938 閱讀 9021

插入 \(x\) 數

刪除 \(x\) 數(若有多個相同的數,因只刪除一個)

查詢 \(x\) 數的排名(排名定義為比當前數小的數的個數 \(+1\) )

查詢排名為 \(x\) 的數

求 \(x\) 的前驅(前驅定義為小於 \(x\),且最大的數)

求 \(x\) 的後繼(後繼定義為大於 \(x\),且最小的數)

敲了一發 splay。中途因為不明原因死迴圈了一個點。

沒什麼好說的,splay 入門可以參考這篇 洛谷**。

#include #include #include using namespace std;

const int n=100010,inf=1e9;

int q,rt;

struct splay

void build()

int pos(int x)

void rotate(int x)

void splay(int x,int f=0)

rotate(x);

} if (!f) rt=x; }

int find(int x)

int pre(int x)

void ins(int x)

if (val[p]==x) cnt[p]++;

else

splay(p); }

void del(int x)

else son[z][0]=0;

pushup(z); pushup(p);

} int get_rank(int x)

int get_val(int k)

splay(p);

return p;

}}splay;

int main()

return 0;

}

洛谷 P3369 模板 普通平衡樹

洛谷傳送門 插入 xx 數 刪除 xx 數 若有多個相同的數,因只刪除一個 查詢 xx 數的排名 排名定義為比當前數小的數的個數 1 1 查...

luogu P3369 模板 普通平衡樹

題目描述 插入 x 數 刪除 x 數 若有多個相同的數,因只刪除一個 查詢 x 數的排名 排名定義為比當前數小的數的個數 1 查詢排名為 x...

題解 P3369 模板 普通平衡樹

在網上某篇神奇的教程和 codesonic 大佬的標程幫助下,我又肝完了leafy tree,跑過來寫篇題解 好像以前寫過一篇? leafy tree由兩種節點組成 輔助節點與葉子節點。 葉子節點儲存值,而輔助節點儲存左右孩子中大的那個值。 注意 輔助節點必定有兩個孩子。 拿插入操作舉例 一路向下遞...