平衡树

FHQ-Treap

例题

洛谷 P3369:【模板】普通平衡树 / 洛谷 P6136:【模板】普通平衡树(数据加强版)

Description

你需要写一个数据结构来支持以下六种操作:

  1. 插入一个数 $x$。
  2. 删除一个数 $x$(若有多个相同的数,只删除一个)。
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$)。
  4. 查询排名为 $x$ 的数。
  5. 求 $x$ 的前驱(前驱定义为小于 $x$,且最大的数)。
  6. 求 $x$ 的后继(后继定义为大于 $x$,且最小的数)。

其中 $1 \leq n \leq 10^5,~|x| \leq 10^7$。

Solution

看代码注释。

Code
/*
    Author: Ruakker
    Date: 2021-04-26 08:19:19
    LastEditTime: 2021-05-14 08:24:50
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
inline ll read(){
    ll x=0,w=1;
    char ch=getchar();
    for (;!isdigit(ch);ch=getchar())
        if (ch=='-') w=-1;
    for (;isdigit(ch);ch=getchar())
        x=x*10+(ch-'0');
    return x*w;
}
void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10);
    putchar(x%10+'0');
}
inline void writeln(ll x){write(x),putchar('\n');}
const int N=1e5+5;
struct Ruakker{
    int sz,son[2],val,weight;
}tr[N];
int tot=0,n,rt,x,y,z;

/* basic operation */
inline int newnode(int val){
    tr[++tot].sz=1,tr[tot].val=val,tr[tot].weight=rand(),tr[tot].son[0]=tr[tot].son[1]=0;
    return tot;
}
inline void calcsize(int cur){
    tr[cur].sz=tr[tr[cur].son[0]].sz+tr[tr[cur].son[1]].sz+1;
}
int merge(int x,int y){ //default:x_val<y_val
    if (!x||!y) return x+y;
    calcsize(x),calcsize(y);
    if (tr[x].weight<tr[y].weight){ //it will do like the small-root heap
        tr[x].son[1]=merge(tr[x].son[1],y),calcsize(x);
        return x;
    }else{
        tr[y].son[0]=merge(x,tr[y].son[0]),calcsize(y);
        return y;
    }
}
void split(int cur,int val,int &x,int &y){
    if (!cur) return x=y=0,void();
    calcsize(cur);
    if (tr[cur].val<=val)   //'<' & '=' then node at the left,'>' at the right
        x=cur,split(tr[cur].son[1],val,tr[cur].son[1],y);else   //left_son tree.val must < val,so let's split the right_son tree.
        y=cur,split(tr[cur].son[0],val,x,tr[cur].son[0]);   //right_son tree.val must > val,so let's split the left_son tree.
    calcsize(cur);
}
inline int kth(int cur,int k){  //get the kth node [id] in tree_cur.
    for (;1;){
        if (k==tr[tr[cur].son[0]].sz+1) //the size include the node itself,so "sz == k+1".
            return cur;
        if (k<=tr[tr[cur].son[0]].sz)
            cur=tr[cur].son[0];
        else{
            k-=tr[tr[cur].son[0]].sz+1;
            cur=tr[cur].son[1];
        }
    }
}
/* end of the basic operation */

inline void ins(int val){
    split(rt,val,x,y),rt=merge(merge(x,newnode(val)),y);
}
inline void del(int val){
    split(rt,val,x,y),split(x,val-1,x,z);
    z=merge(tr[z].son[0],tr[z].son[1]);
    rt=merge(merge(x,z),y);
}
inline void getrank(int val){
    split(rt,val-1,x,y),writeln(tr[x].sz+1),rt=merge(x,y);
}
inline void getnum(int rk){
    writeln(tr[kth(rt,rk)].val);
}
inline void getpre(int val){
    split(rt,val-1,x,y),writeln(tr[kth(x,tr[x].sz)].val),rt=merge(x,y);
}
inline void getsuc(int val){
    split(rt,val,x,y),writeln(tr[kth(y,1)].val),rt=merge(x,y);
}
signed main(){
    srand(time(0));
    for (int T=read();T--;){
        int opt=read(),u=read();
        if (opt==1) ins(u);
        if (opt==2) del(u);
        if (opt==3) getrank(u);
        if (opt==4) getnum(u);
        if (opt==5) getpre(u);
        if (opt==6) getsuc(u);
    }
    return 0;
}

洛谷 P3391:【模板】文艺平衡树

Description

您需要写一种数据结构,来维护一个长度为 $n~(1 \leq n \leq 10^5)$ 的有序数列。

其中需要提供以下共 $m~(1 \leq n,m \leq 10^5)$ 次操作:

  • 翻转一个区间。

例如原有序序列是 $\texttt{5 4 3 2 15 4 3 2 1}$,翻转区间是 $[2,4]$ 的话,结果是 $\texttt{5 2 3 4 15 2 3 4 1}$。

Solution
Code
/*
    Author: Ruakker
    Date: 2021-05-13 20:52:45
    LastEditTime: 2021-05-14 08:23:05
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
inline ll read(){
    ll x=0,w=1;
    char ch=getchar();
    for (;!isdigit(ch);ch=getchar())
        if (ch=='-') w=-1;
    for (;isdigit(ch);ch=getchar())
        x=x*10+(ch-'0');
    return x*w;
}
void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10);
    putchar(x%10+'0');
}
inline void writeln(ll x){write(x),putchar('\n');}
const int N=1e5+5;
struct Ruakker{
    int sz,son[2],val,weight;
    bool rev;
}tr[N];
int tot,n,m,rt,a,b,c,d;
inline int newnode(int val){return tr[++tot].sz=1,tr[tot].son[0]=tr[tot].son[1]=0,tr[tot].val=val,tr[tot].weight=rand(),tr[tot].rev=0,tot;}
inline void update(int cur){    //here we not only recalc the size of the node, but also reverse the son of the node :)
    tr[cur].sz=tr[tr[cur].son[0]].sz+tr[tr[cur].son[1]].sz+1;
    if (cur&&tr[cur].rev){
        tr[cur].rev^=1;
        std::swap(tr[cur].son[0],tr[cur].son[1]);
        tr[tr[cur].son[0]].rev^=1,tr[tr[cur].son[1]].rev^=1;
    }
}

int merge(int x,int y){
    if (!x||!y) return x+y;
    update(x),update(y);
    if (tr[x].weight<tr[y].weight)
        return tr[x].son[1]=merge(tr[x].son[1],y),update(x),x;else
        return tr[y].son[0]=merge(x,tr[y].son[0]),update(y),y;
}
void split(int cur,int size,int &x,int &y){ //notice that this time the split is depending on the size of the tree
    if (!cur) return x=y=0,void();
    update(cur);
    if (tr[tr[cur].son[0]].sz>=size)    //if the left-son tree's size is larger,then
        y=cur,split(tr[cur].son[0],size,x,tr[cur].son[0]);else
        x=cur,split(tr[cur].son[1],size-tr[tr[cur].son[0]].sz-1,tr[cur].son[1],y);
    update(cur);
}
inline void ins(int val){split(rt,val,a,b),rt=merge(merge(a,newnode(val)),b);}

inline void rev(int l,int r){
    split(rt,r,a,b),split(a,l-1,c,d);       //the tree_d is the interval [l,r]
    tr[d].rev^=1,rt=merge(merge(c,d),b);    //reverse the interval and merge it :)
}

void print(int cur){
    if (!cur) return;
    update(cur);
    print(tr[cur].son[0]);
    if (tr[cur].val>=1&&tr[cur].val<=n)
        write(tr[cur].val),putchar(' ');
    print(tr[cur].son[1]);
}

signed main(){
    srand(time(0));
    n=read(),m=read();
    for (int i=1;i<=n;ins(i++));
    for (;m--;){
        int l=read(),r=read();
        rev(l,r);
    }
    print(rt),putchar('\n');
    return 0;
}

评论

  1. legendgod
    Windows Chrome 91.0.4472.124
    3月前
    2021-7-25 16:21:53

    $tql tql$

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇