首页 > 其他 > 详细

模版整理(数据结构)【待更新】

时间:2015-12-07 22:25:08      阅读:236      评论:0      收藏:0      [点我收藏+]

treap(bzoj3224)

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 200500
using namespace std;
int n,op,root,ans,x;
struct T{
int l[maxn],r[maxn],s[maxn],v[maxn],w[maxn],rnd[maxn];  
int cnt;
void up(int t){
    s[t]=s[l[t]]+s[r[t]]+w[t];
}
void rt(int &t){
    int k=l[t]; l[t]=r[k]; r[k]=t; up(t); up(k); t=k;
}
void lt(int &t){
    int k=r[t]; r[t]=l[k]; l[k]=t; up(t); up(k); t=k;
}
void insert(int &t,int x){
    if (t==0){
        t=++cnt; v[t]=x; s[t]=w[t]=1; rnd[t]=rand();
        return;
    }
    s[t]++;
    if (x==v[t]) w[t]++;
    else if (x<v[t]) {
        insert(l[t],x);
        if (rnd[l[t]]<rnd[t]) rt(t); 
    }
    else {
        insert(r[t],x); 
        if (rnd[r[t]]<rnd[t]) lt(t);
    }
}
void del(int &t,int x){
    if (t==0) return;
    if (x==v[t]){
        if (w[t]>1) {w[t]--; s[t]--;return;}  //!!!!!!!!!!!!
        if (l[t]*r[t]==0) t=l[t]+r[t];
        else if (rnd[l[t]]<rnd[r[t]]) rt(t),del(t,x);
        else lt(t),del(t,x);
    }
    else if (x<v[t]) s[t]--,del(l[t],x); 
    else s[t]--,del(r[t],x);
}
int rank(int t,int x){
    if (t==0) return 0;
    if (x==v[t]) return s[l[t]]+1;
    else if (x<v[t]) return rank(l[t],x);
    else return s[l[t]]+w[t]+rank(r[t],x);
}
int select(int t,int k){
    if (t==0) return 0;
    if (k>=s[l[t]]+1&&k<=s[l[t]]+w[t]) return v[t];
    else if (k<s[l[t]]+1) return select(l[t],k);
    else return select(r[t],k-s[l[t]]-w[t]);
}
void pred(int t,int x){
    if (t==0) return;
    if (v[t]<x){
        ans=v[t]; pred(r[t],x);
    }
    else pred(l[t],x);
}
void succ(int t,int x){
    if (t==0) return ;
    if (v[t]>x){
        ans=v[t]; succ(l[t],x);
    }
    else succ(r[t],x);
}
}treap;
int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if (ch==-) f=-1; ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-0; ch=getchar();}
    return x*f;
}
int main(){
//  freopen("in.txt","r",stdin);
    n=read();
    rep(i,1,n){
        op=read();
        if (op==1) {x=read(); treap.insert(root,x);}
        if (op==2) {x=read(); treap.del(root,x);}
        if (op==3) {x=read(); printf("%d\n",treap.rank(root,x));}
        if (op==4) {x=read(); printf("%d\n",treap.select(root,x));}
        if (op==5) {x=read(); ans=0; treap.pred(root,x); printf("%d\n",ans);}
        if (op==6) {x=read(); ans=0; treap.succ(root,x); printf("%d\n",ans);}
    }
    return 0;
}

 

模版整理(数据结构)【待更新】

原文:http://www.cnblogs.com/ctlchild/p/5027520.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!