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

· · 题解

Treap题解

看了好几篇题解都没有用Treap做的，于是来分享一下我的Treap打法叭

这个题似乎是个平衡树板子的亚子，但是似乎很多人都是用了其他的大佬算法，数据好像也水的一批，但是如果是作为平衡树的模板来练练手的话是比较合适的选择。

我这里介绍的是Treap的做法，用起来还是比较方便的，毕竟只需要插入和查询。

根据题意，我们显然是要维护两个值：比当前x小的最大值，比当先x大的最小值。

我们先把第一个数直接插入，因为第一个数的最小波动值一定是自己。然后把之后的每个数查询两次，分别找到我们要维护的两个值，找到最小波动值

        minx=query_las(x);
        maxx=query_net(x);
        xx=min(x-minx,maxx-x);
        ans+=xx;

有一点要注意，我们在查询是先把要找的变量赋成一个极值，这样就可以保证在找不到的情况下返回一个绝对不会选的值

因为我们只要查询和插入，所以我们不用维护子树大小size，所以代码打起来会方便很多

有关于平衡树的更多操作，可以做一做【模板】普通平衡树

话不多说，上码

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
const int INF=1e7+10;
int ans=0,x;
int n,root,tot,val[N],a[N][2],ran[N],cnt[N];

int add(int v) //加入新的数 
{
    tot++;
    val[tot]=v;//权值 
    ran[tot]=rand();//随机的优先级 
    cnt[tot]=1; //cnt代表当先数值为x的值的个数 
    return tot;
}

void build(int v) //看似没什么用的预处理 
{
    root=add(v);
}

void rotate(int &k,int v) //旋转操作，k代表树根，v=0是左旋，v=1是右旋 
{
    int t=a[k][!v];
    a[k][!v]=a[t][v];
    a[t][v]=k;
    k=t;
}

void insert(int &k,int v) //插入操作，k为树根，v为要插入的值 
{
    if(!k) 
    {
        k=add(v); //如果找不到了就建新的点 
        return;
    }
    if(v==val[k]) cnt[k]++; 
    else
    {
        int d=v<val[k]?0:1; //找到要找的方向 
        insert(a[k][d],v);
        if(ran[k]>ran[a[k][d]]) rotate(k,!d); //如果优先级更小的话旋转（注意是反方向的） 
    }
}

int query_las(int v) //查询比x小的 
{
    int k=root,last=-INF; // 如果找不到就返回一个极小值（就是一定不会选的值） 
    while(k)
    {
        if(val[k]<=v) last=val[k],k=a[k][1]; 
        else k=a[k][0];
    }
    return last;
}

int query_net(int v) // 查询比x大的 
{
    int k=root,net=INF; //同上 
    while(k)
    {
        if(val[k]>=v) net=val[k],k=a[k][0];
        else k=a[k][1];
    }
    return net;
}

int main()
{
    scanf("%d%d",&n,&x);
    build(x);
    ans+=x;
    for(int i=2,minx,maxx,xx;i<=n;i++)
    {
        scanf("%d",&x);
        minx=query_las(x);
        maxx=query_net(x);
        xx=min(x-minx,maxx-x);
        ans+=xx;
        insert(root,x);
    }
    printf("%d\n",ans);
    return 0;
} 
//没辽