P2234 [HNOI2002]营业额统计题解

· · 题解

链接

看到平衡树的标签就不放心

看到dalao们各种牛逼的LCT，splay···

还是离线打链表吧

首先排序，然后插入链表

r[i]表示原来的a[i]在链表中的位置

倒序处理，把r[i]的ans贡献算出来，然后删除r[i]指向的位置

为什么这样可行呢？

因为是离线+排序，所以每个元素之间的关系是已知的
倒序处理时，对于每个a[i]，链表就是前i个元素组成的
所以不用我说了吧~~

复杂度O(NlogN)，实测68ms

#pragma GCC optimize(2)//O(2)优化，参加NOIp时别用
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
struct node
{   int pre,next;
    #define l(x) b[b[x].pre]
    #define r(x) b[b[x].next]
}b[32768];
struct data{int d,rank;}a[32768];
int r[32768],n,ans;
bool cmp(const data &x,const data &y){return x.d<y.d||(x.d==y.d&&x.rank<y.rank);}
inline void del(int x)
{r(x).pre=b[x].pre;l(x).next=b[x].next;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i].d),a[i].rank=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        r[a[i].rank]=i;
        if(i!=n)b[i].next=i+1;
        b[i].pre=i-1;
    }
    for(int i=n,x,j,k;i;i--,j=0,k=0)
    {
        x=r[i];
        if(b[x].pre)j=abs(a[b[x].pre].d-a[x].d);else j=2147483647/3;
        if(b[x].next)k=abs(a[b[x].next].d-a[x].d);else k=2147483647/3;
        if(i!=1)ans+=min(j,k);else ans+=a[x].d;
        del(x);r[i]=0;
    }
    printf("%d",ans);
    return 0;
}

谢谢你们看到最后~~~