CF1534G solution

E_huan · 2022-07-27 08:37:13 · 题解

前言： 1.管理员大大最仁慈善良可爱了对吧!(第4次了！求过！）

2.之前写这道题的时候看了很久题解才懂,所以自己又整理了一遍，本篇题解内容有不少借鉴洛谷题解区其它题解的，加上了自己的理解(解释了一下当时自己没看懂的地方),所以比较长(图都是自己画的哈哈)

3.如果蒟蒻讲错了,发现问题的神犇请教教我(谢谢!!)

思路：slope trick

一个点 \,P\, 到一条路径（这条路径的点满足纵坐标随横坐标单调递增，即只能向上向右走）的切比雪夫距离最小肯定是经过这个点的斜率为 \,-1\, 的直线与路径的交点\,Q\,间的距离（因为路径上不会有点到P的横纵距离都比 \,Q\,小,而 \,Q\, 到 \,P\, 的横纵距离相等,\,\text{MAX}=\text{MIN}\, )

考虑将点以\,x+y\,为序排列好。这样的话，一条路径总会按序经过每个点所在的斜率为\,-1\,的直线。于是做一个暴力的DP,即设 \,f_{i,x}\, 为当前\,DP\,到第\,i\,个点，当前横坐标为x的最小代价。

转移式：

为什么是这个范围，我们化简一下：

左式含义就是\,x'\,是在\,x\,左边

而\,x+y=x_i+y_i, x'+y'=x_{i-1} + y_{i-1}\,

带入右式得到\,y\geqslant y'\,

所以就是枚举所有在上一个点对应的直线上(过上一个点且斜率为\,-1\,的直线),且在当前点左下方（左方 下方）的点。

考虑\,f_i\,以第二维作为横坐标时的图像。我们可以有一个结论：已知 \,f(x)\,为定义域为\,\mathbb{R}\, 且连续的函数，令 \,g(x)=\min_{x'\in[x-x_0,x+x_0]}{f(x')}\,，其中\,x_0\,为一定值，则\,g(x)\,为连续函数.又因为\,|x-x_i|\,是下凸函数(绝对值函数那个，先向右下直线，再向右上直线，斜率分别是\,-1,1\,)，而下凸函数与下凸函数的和还是下凸函数，所以\,f_i\,也为下凸函数。

接下来我们考虑维护这个下凸壳。

取\,\min\, 操作相当于将\,f_i\,的最低点向右拉长\,(x_i+y_i)-(x_{i-1}+y_{i-1})\,的距离，右部分同时平移，其余不变

如上图，黑色的是这个函数，所有红色标出的区间内的最小值都是不同的，左部是线段右端点横坐标对应的函数上的点，右部是线段左端点横坐标对应的函数上的点。而中间紫色部分都对应的是最低点，所以画出\,\text{MIN}\,图像其实相当于是原图中间部分拉长（一条水平线），右边向右平移。（如下图）

那么为什么是拉长\,x_i+y_i-x_{i-1}-y_{i-1}\,呢？因为“\,x'\in[x-(x_i+y_i)+(x_{i-1}+y_{i-1}),x]\, ”,即\,x'\,取值范围的大小是\,x_i+y_i-x_{i-1}-y_{i-1\,},也就是图中红色紫色线段的长度是\,x_i+y_i-x_{i-1}-y_{i-1}\,,而这个长度正是新图上水平线的长度

“拉长”在代码上要用懒标记实现

至于加入一个\,|x-x_i|\,我们可以做这样一件事，定义一个有序可重集中的一个元素表示当前凸壳在此处斜率减少了\, 1\,。

于是我们只需维护这个可重集，就可以维护好\,|x-x_i|\,了（这个套路非常常用）

具体实现上，每次加入一个点分三类讨论，若当前\,x_i\,在最低点左边/最低点/最低点右边。

在其左时,\,x_i\,的左边斜率都减一,而右边都加一,等于在 \,x_i\,的位置减少了\,2\,,所以我们朝左部分可重集加入两个 \,x_i\,,同时最左边的最低点此时已经不再是最低点,所以将其放入右部分可重集里。放入右部分可重集时要注意我们打了全局的右部分平移量标记,放入前要先减去此标记,不然拿出来时就不是真实值了。其余情况同理维护一下。此时\,i\,的贡献就是离它最近的最低点的贡献。

用堆就可以维护,时间复杂度瓶颈在于堆的使用,\,\mathcal{O}(n\log n)\,

左边用大根堆,由于整体是下凸壳,放在左部的是单调递减的,横坐标最大的对应的就是最小值的位置。同理,右部单调递增,用小根堆。

此外还有一种方法是切比雪夫距离转曼哈顿距离

这也是一个常用的\,\text{trick:} (x,y)→(x+y,x-y)\,前者的切比雪夫距离就是后者曼哈顿距离的一半

曼哈顿距离也有个性质,一个点到一条确定的路径（类似函数的那种，每个\,X\,只对应\,1\,个\,Y\,）上的所有点的曼哈顿距离中,到和它横坐标向等的点的曼哈顿距离最小

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+10;
int n;
typedef pair<int,int> pii;
pii a[N];
typedef long long ll;
ll ans;
priority_queue<int> L;
priority_queue<int,vector<int>,greater<int> > R;
#define sum first
#define x second
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[i]={x+y,x};
    }
    sort(a+1,a+n+1);
    L.push(a[1].x);
    R.push(a[1].x);
    int tagr=0;
    for(int i=2;i<=n;i++)
    {
        tagr+=a[i].sum-a[i-1].sum;//tagr表示全局的有部分平移量标记
        int l=L.top(),r=R.top()+tagr,x=a[i].x;
        if(x<l)
        {
             L.pop(),R.push(l-tagr);
             L.push(x),L.push(x);
             ans+=l-x;
        }// xi在最低点左边
        else if(x>r) 
        {
            R.pop(),L.push(r);
            R.push(x-tagr),R.push(x-tagr);
            ans+=x-r;
        }// xi在最低点
        else
        {
            L.push(x),R.push(x-tagr);
        }// xi在最低点右边
    }
    printf("%lld\n",ans);
    return 0;
}