@zzzc18 2017-06-18T10:24:37.000000Z 字数 1715 阅读 1188

# bzoj1588 Treap

bzoj Treap

#include<cmath>#include<cstdio>#include<cstdlib>#include<algorithm>#define MAXN 50000#define inf 0x7fffffffusing namespace std;struct T{    int ls,rs,sz,num,val,rd;    T(){        val=inf;    }}tree[MAXN];int ans,size,root;int n,tot;int x;int Find(const int &k,int x){    if(tree[k].val==x)return k;    if(tree[k].val<x)        return Find(tree[k].rs,x);    else        return Find(tree[k].ls,x);}void update(int x){    tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;}void rotate_l(int &k){    int y=tree[k].rs;    tree[k].rs=tree[y].ls;    tree[y].ls=k;    tree[y].sz=tree[k].sz;    update(k);    k=y;}void rotate_r(int &k){    int y=tree[k].ls;    tree[k].ls=tree[y].rs;    tree[y].rs=k;    tree[y].sz=tree[k].sz;    update(k);    k=y;}void insert(int &k,int v){    if(k==0){        size++;k=size;        tree[k].sz=tree[k].num=1;        tree[k].val=v;        tree[k].rd=rand();        return;    }    tree[k].sz++;    if(tree[k].val==v){        tree[k].num++;    }    else if(tree[k].val<v){        insert(tree[k].rs,v);        if(tree[tree[k].rs].rd<tree[k].rd)rotate_l(k);    }    else{        insert(tree[k].ls,v);        if(tree[tree[k].ls].rd<tree[k].rd)rotate_r(k);    }}void pred(const int &k,int v){    if(k==0)return;    if(tree[k].val<v){        ans=k;        pred(tree[k].rs,v);    }    else        pred(tree[k].ls,v);}void succ(const int &k,int v){    if(k==0)return;    if(tree[k].val>v){        ans=k;        succ(tree[k].ls,v);    }    else        succ(tree[k].rs,v);}int main(){    freopen("bzoj.in","r",stdin);    freopen("out.out","w",stdout);    scanf("%d",&n);    int i;    scanf("%d",&x);    insert(root,x);    tot=x;    for(i=2;i<=n;i++){        scanf("%d",&x);        insert(root,x);        int loc=Find(root,x);        if(tree[loc].num>1){            ans=0;        }        else{            int s,p;            ans=0;            pred(root,x);            if(tree[ans].val!=inf)                p=abs(x-tree[ans].val);            else                p=inf;            ans=0;            succ(root,x);            if(tree[ans].val!=inf)                s=abs(x-tree[ans].val);            else                s=inf;            ans=min(p,s);        }        tot+=ans;        printf("ans: %d\n",ans);    }    printf("%d\n",tot);    return 0;}

• 私有
• 公开
• 删除