Treap
|
847
|
0
|
未分类

711 字
|
26 分钟

Treap

treap是啥，是一种平衡树，tree+heap

众所周知，二叉平衡树一旦退化，复杂度将会很可怕。

treap则给每一个节点附上了一个随机的值，然后利用旋转操作，让这个二叉搜索树同时也满足堆的性质。期望下可以达到$O(nlog_n)$的复杂度了。

具体怎么实现呢

大部分的操作和一般的二叉搜索树一样。

插入

void insert(int &p,int v){
    if(!p){
        p=New(v);
        return ;
    }
    tr[p].size++;
    if(v==tr[p].v){
        tr[p].cnt++;
        return ;
    }
    if(v<tr[p].v){
        insert(tr[p].l,v);
        if(tr[p].rv<tr[tr[p].l].rv){
            rr(p);
        }
        return ;
    }else{
        insert(tr[p].r,v);
        if(tr[p].rv<tr[tr[p].r].rv){
            lr(p);
        }
    }
    return ;
}

可以注意到多了判断儿子的随机权值是否满足堆的过程。

删除

void del(int &p,int v){
    if(!p) return ;
    tr[p].size--;
    if(tr[p].v==v){
        if(tr[p].cnt>1){
            tr[p].cnt--;
            return ;
        }
        if(!tr[p].l||!tr[p].r){
            p=tr[p].l+tr[p].r;
        }else{
            if(tr[tr[p].l].rv>tr[tr[p].r].rv){
                rr(p);
                del(tr[p].r,v);
            }else{
                lr(p);
                del(tr[p].l,v);
            }
        }
        return ;
    }
    if(v<tr[p].v){
        del(tr[p].l,v);
    }else{
        del(tr[p].r,v);
    }
}

在连接左右儿子的时候需要判断是否满足堆的性质

Lisa

最经典的模板题了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
int f;
int x;
struct tr{
    int l;
    int r;
    int v;
    int cnt;
    int rv;
    int size;
}tr[200005];
int ro;
int cnt;
int New(int val){
    tr[++cnt].l=0;
    tr[cnt].r=0;
    tr[cnt].v=val;
    tr[cnt].cnt=1;
    tr[cnt].size=1;
    tr[cnt].rv=rand();
    return cnt;
}
void update(int x){
    tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+tr[x].cnt;
}
void rr(int &p){
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    tr[q].size=tr[p].size;
    update(p);
    p=q;
}
void lr(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    tr[q].size=tr[p].size;
    update(p);
    p=q;
}
void insert(int &p,int v){
    if(!p){
        p=New(v);
        return ;
    }
    tr[p].size++;
    if(v==tr[p].v){
        tr[p].cnt++;
        return ;
    }
    if(v<tr[p].v){
        insert(tr[p].l,v);
        if(tr[p].rv<tr[tr[p].l].rv){
            rr(p);
        }
        return ;
    }else{
        insert(tr[p].r,v);
        if(tr[p].rv<tr[tr[p].r].rv){
            lr(p);
        }
    }
    return ;
}
void del(int &p,int v){
    if(!p) return ;
    tr[p].size--;
    if(tr[p].v==v){
        if(tr[p].cnt>1){
            tr[p].cnt--;
            return ;
        }
        if(!tr[p].l||!tr[p].r){
            p=tr[p].l+tr[p].r;
        }else{
            if(tr[tr[p].l].rv>tr[tr[p].r].rv){
                rr(p);
                del(tr[p].r,v);
            }else{
                lr(p);
                del(tr[p].l,v);
            }
        }
        return ;
    }
    if(v<tr[p].v){
        del(tr[p].l,v);
    }else{
        del(tr[p].r,v);
    }
}
int getpre(int v){
    int p=ro;
    int res=0;
    while(p){
        if(tr[p].v<v){
            res=tr[p].v;
            p=tr[p].r;
        }else{
            p=tr[p].l;
        }
    }
    return res;
}
int getsuf(int v){
    int p=ro;
    int res=0;
    while(p){
        if(tr[p].v<v){
            res=tr[p].v;
            p=tr[p].r;
        }else{
            p=tr[p].l;
        }
    }
    return res;
}
int getrank(int p,int v){
    if(!p) return 0;
    if(tr[p].v==v) return tr[tr[p].l].size+1;//这里扔的是size，这里扔的是左儿子
    if(tr[p].v<v) return getrank(tr[p].r,v)+tr[tr[p].l].size+tr[p].cnt;
    if(tr[p].v>v) return getrank(tr[p].l,v); 
}
int getval(int p,int v){
    if(!p) return 0;
    if(tr[tr[p].l].size>=v) return getval(tr[p].l,v);
    if(tr[tr[p].l].size+tr[p].cnt>=v) return tr[p].v;
    return getval(tr[p].r,v-tr[p].cnt-tr[tr[p].l].size);
}
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        read(f);
        read(x);
        if(f==1) insert(ro,x);
        if(f==2) del(ro,x);
        if(f==3) printf("%dn",getrank(ro,x));
        if(f==4) printf("%dn",getval(ro,x));
        if(f==5) printf("%dn",getpre(x));
        if(f==6) printf("%dn",getsuf(x));

    }
    return 0;
}

Rose只需要询问前驱和后继

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
struct tr{
    int l;int r;
    int v;
    int cnt;int rv;
}tr[500000];
int ro;
int cnt;
int a[500000];
int New(int v){
    tr[++cnt].l=0;
    tr[cnt].r=0;
    tr[cnt].v=v;
    tr[cnt].cnt=1;
    tr[cnt].rv=rand();
    return cnt;
}
void rr(int &p){
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    return ;
}
void lr(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    return ;
}
void insert(int &p,int v){
    if(!p){
        p=New(v);
        return ;
    }
    if(tr[p].v==v){
        tr[p].cnt++;
        return ;
    }
    if(tr[p].v<v){
        insert(tr[p].r,v);
        if(tr[p].rv<tr[tr[p].r].rv){
            lr(p);
        }
        return ;
    }else{
        insert(tr[p].l,v);
        if(tr[p].rv<tr[tr[p].l].rv){
            rr(p);
        }
        return ;
    }
}
int getpre(int v){
    int p=ro;
    int res=999999999;
    while(p){
        if(tr[p].v<=v){
            res=tr[p].v;
            p=tr[p].r;
        }else{
            p=tr[p].l;
        }
    }
    return res;
}
int getsuf(int v){
    int p=ro;
    int res=999999999;
    while(p){
        if(tr[p].v>=v){
            res=tr[p].v;
            p=tr[p].l;
        }else{
            p=tr[p].r;
        }
    }
    return res;
}
int ans;
int main(){
    read(n);
    read(ans);
    insert(ro,ans);
    for(int i=2;i<=n;++i){
        read(a[i]);

        //if(i!=1)
        ans+=min(abs(a[i]-getpre(a[i])),abs(getsuf(a[i])-a[i]));
        //else{
            //ans=a[i];
    //  }
        insert(ro,a[i]);
    }
    cout<<ans;
    return 0;
}

Jennie

注意一下前驱后缀的返回值

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int t;
int ro;
int cnt;
struct tree{
    int l;
    int r;
    int cnt;
    int v;
    int rv;
}tr[1000005];
int New(int x){
    tr[++cnt].l=0;
    tr[cnt].r=0;
    tr[cnt].cnt=1;
    tr[cnt].v=x;
    tr[cnt].rv=rand();
    return cnt;
}
void rr(int& p){
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    //tr[p].size=tr[q].size();
    p=q;
}
void lr(int& p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    //tr[p].size=tr[q].size();
    p=q;
}
void insert(int &p,int v){
    if(!p) {
        p=New(v);
        return ;
    }
    if(v==tr[p].v){
        tr[p].cnt++;
        return ;
    }
    if(v<tr[p].v){
        insert(tr[p].l,v);
        if(tr[tr[p].l].rv>tr[p].rv){
            rr(p);
        }
        return ;
    }else{
        insert(tr[p].r,v);
        if(tr[tr[p].r].rv>tr[p].rv){
            lr(p);
        }
        return ;
    }
}
int cntt[2];
void del(int &p,int v){
    if(!p){
        return ;
    }
    if(tr[p].v==v){
        if(tr[p].cnt>1){
            tr[p].cnt--;
            return ;
        }
        if(!tr[p].l||!tr[p].r){
            p=tr[p].l+tr[p].r;
        }else{
            if(tr[tr[p].l].rv>tr[tr[p].r].rv){
                rr(p);
                del(tr[p].r,v);
            }else{
                lr(p);
                del(tr[p].l,v);
            }
        }
        return ;
    }
    if(v<tr[p].v){
        del(tr[p].l,v);
    }
    if(v>tr[p].v){
        del(tr[p].r,v);
    }
}
int getpre(int v){
    int p=ro;
    int res=-999999999;
    while(p){
        if(tr[p].v<=v){
            res=tr[p].v;
            p=tr[p].r;
        }else{
            p=tr[p].l;
        }
    }
    return res;
}
int getsuf(int v){
    int p=ro;
    int res=999999999;
    while(p){
        //cout<<p<<endl;
        if(tr[p].v>=v){
            res=tr[p].v;
            p=tr[p].l;
        }else{
            p=tr[p].r;
        }
    }
    return res;
}
int n;
int a,b;
int ans;
int mod=1000000;
signed main(){
    read(n);
    for(int i=1;i<=n;++i){
        //cout<<i<<endl;
        read(a);read(b);
        if(cntt[a^1]){
            int pp=getpre(b);
            int ss=getsuf(b);
        //  cout<<"F";
            if(b-pp<=ss-b){
                ans+=b-pp;
                ans%=mod;
                del(ro,pp);
            }else{
                ans+=ss-b;
                ans%=mod;
                del(ro,ss);
            }
        //  cout<<ans<<endl;
            cntt[a^1]--;
        }else{
            insert(ro,b);
            cntt[a]++;
        }
    }
    cout<<ans%mod;
    return 0;
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇