henrytb 的博客

henrytb 的博客

题解 P2234 【[HNOI2002]营业额统计】

posted on 2019-08-03 19:46:23 | under 题解 |

看见没什么人用fhq-treap做这题,赶紧水一发~


今天早上刚自己百度学了fhq-Treap(自认为比较容易理解),于是自己写了几道题。。。

fhq-treap与treap的区别就在于它维护平衡不用什么左旋右旋转来转去,而是用分裂合并两个操作来维护

而这道题呢只需要读入同时对每个节点寻找前驱/后继中波动值最小的一个,这显然是平衡树模板 (然而有很多人用set秒切此题)

具体实现见呆码:

#include <bits/stdc++.h>
#define spilt split
#define ls(rt) T[rt].lc
#define rs(rt) T[rt].rc
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int INF=0x3f3f3f3f;
int n,tot=0;
struct node{
    int val,rnk,lc,rc,sz;
}T[40005];
void update(int rt){T[rt].sz=T[ls(rt)].sz+T[rs(rt)].sz+1;}
int add(int val){
    T[++tot].val=val;
    ls(tot)=rs(tot)=0;
    T[tot].sz=1;
    T[tot].rnk=rand();
    return tot;
}
void split(int rt,int &a,int &b,int val){
    if(!rt){a=b=0;return;}
    if(T[rt].val<=val){
        a=rt;
        split(rs(rt),rs(a),b,val);
    } else {
        b=rt;
        split(ls(rt),a,ls(b),val);
    }
    update(rt);
}
void merge(int &rt,int a,int b){
    if(a==0||b==0){
        rt=a+b;
        return;
    }
    if(T[a].rnk<T[b].rnk){
        rt=a;
        merge(rs(rt),rs(a),b);
    } else {
        rt=b;
        merge(ls(rt),a,ls(b));
    }
    update(rt);
}
int kth(int rt,int k){
    while(k!=T[ls(rt)].sz+1){
        if(k<T[ls(rt)].sz+1) rt=ls(rt);
        else{
            k-=T[ls(rt)].sz+1;
            rt=rs(rt);
        }
    }
    return T[rt].val;
}
void insert(int &rt,int val){
    int a=0,b=0,newnode=add(val);
    spilt(rt,a,b,val);
    merge(a,a,newnode);
    merge(rt,a,b);
}
int pre(int &rt,int val){
    int a=0,b=0;
    split(rt,a,b,val);
    int ans=kth(a,T[a].sz);
    merge(rt,a,b);
    return ans;
}
int scc(int &rt,int val){
    int a=0,b=0;
    split(rt,a,b,val-1);
    int ans=kth(b,1);
    merge(rt,a,b);
    return ans;
}
int main(){
    int root=1,ans=0;
    srand(19260817);
    scanf("%d",&n);
    add(INF);
    T[root].sz=0;
    insert(root,-INF);
    rep(i,1,n){
        int x;
        scanf("%d",&x);
        if(i!=1)ans+=min(abs(x-pre(root,x)),abs(x-scc(root,x)));
        else ans=x;
        insert(root,x);
    }
    printf("%d",ans);
    return 0;
}