bzoj1588 Treap

bzoj Treap

传送门

这题读了$n$久才读懂，其实就是插入一个数之后查它的前驱和后继，取更小的，另外如果先前已经插入过一个数，波动就是为0；

使用Treap实现。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MAXN 50000
#define inf 0x7fffffff
using 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;
}