P2234 营业额统计 题解

· · 题解

题意简述

设 f(j)=\min_{i=1}^{j-1}\{|x_j-x_i|\}，求 \sum_{i=1}^{n}f(i)，特别的，f(1)=x_1。

对于绝对值，尝试分类讨论。

\text{1. 若 }x_j \ge x_i\text{,} \begin{aligned} f(j) &= \min_{i=1}^{j-1} \{ x_j - x_i \} \\ &= x_j - \max_{i=1}^{j-1} \{ x_i \} \\ \\ \end{aligned} \text{2. 若 }x_j \le x_i\text{,} \begin{aligned} f(j) &= \min_{i=1}^{j-1} \{ x_i - x_j \} \\ &= - x_j - \max_{i=1}^{j-1} \{ - x_i \} \\ \end{aligned} \text{设 }x'=-x,\text{则条件变成若 }x'_j \ge x'_i f(j)=x'_j-\max_{i=1}^{j-1}\{ x'_i\} \text{与 1. 形式一致}

现在考虑怎么维护比第 j 个数早出现且小于等于 x_j 的第一个数。
这是一个很二维偏序的式子（i<j 且 x_i\le x_j），所以可以用 CDQ 分治 解决。

复杂度 T(n)=2T(\dfrac{n}{2})+O(n)=O(n\log{n})

#include <iostream>
using namespace std;
const int N=32768;
const int INF=1<<30;
inline int read()
{
    int x=0;bool w=0;char ch=0; 
    while(ch<'0'|ch>'9'){w|=(ch=='-');ch=getchar();}
    while(ch>='0'&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return w?-x:x;
}
struct cdq{int x,tag;}p[N],q[N],tmp[N];int ans[N];
void solve(int l,int r,cdq*a)
{
    if(l==r)return;int i=l,m=l+r>>1,j=m+1,tot=l,maxn=-INF;solve(l,m,a);solve(m+1,r,a);
    while(i<=m&j<=r)
    {
        if(a[i].x<=a[j].x)maxn=a[i].x,tmp[tot++]=a[i++];
        else ans[a[j].tag]=min(ans[a[j].tag],a[j].x-maxn),tmp[tot++]=a[j++];
    }
    while(i<=m)tmp[tot++]=a[i++];
    while(j<=r)ans[a[j].tag]=min(ans[a[j].tag],a[j].x-maxn),tmp[tot++]=a[j++];
    for(i=l;i<=r;i++)a[i]=tmp[i];
}
int main()
{
    int n=read(),sum=0;
    for(int i=1;i<=n;i++)ans[i]=INF,p[i].tag=q[i].tag=i,p[i].x=read(),q[i].x=-p[i].x;
    ans[1]=p[1].x;
    solve(1,n,p);solve(1,n,q);
    for(int i=1;i<=n;i++)sum+=ans[i];
    cout<<sum;
    return 0;
}
{\color{#66ccff}双倍经验}