[CTSC2009] 序列变换

· · 题解

写这篇题解的主要目的是好好普及下 \mathrm{slope\ trick} 的答案构造，因为通过观察网上题解，疑似都没说清楚为啥是对的，甚至克拉丽丝特判了数据点才过的...所以俺写了这篇题解。

题意：给出一个序列 a 和三个正整数 mx,p,q，要求构造一个序列 b，使得 \sum_{i=1}^n |a_i-b_i| 最小的同时，满足 b_i\in [b_{i+1}-q,b_{i+1}-p]，且必须满足 1\leq b_i\leq mx。

题解：一道有范围限制且要构造方案的 \mathrm{slope\ trick} 题。

首先注意到 1,p+1,2p+1,\cdots,(n-1)p+1 一定是一组解，题目有保证，这也就说明了一定有解。

考虑一个暴力 \mathrm{dp}，设 f_{i,j} 表示当前计算到第 i 个数，当前选择的 b_i 是 j 的最小贡献，显然有转移

f_{i,j}=\min_{k\in [j-q,j-p]} f_{i-1,k}+|j-a_i|

好像和平时遇到的 \mathrm{slope\ trick} 都没有区别，其实是有的。平日里遇到的，j 的范围都是 (-\infty,\infty)，但这道题并不是。在这道题中，特意限定了 j 的范围是 [1,mx]。这意味着什么呢？

我们继续考虑 \mathrm{slope\ trick} 的那一套逻辑，把 f_{i,j} 看成是 j 的函数，此刻取 \min 等价于凸包平移加底部拉长的一个过程，但是由于 j 有限制，这意味在算完第一个数后，凸包在 [mx+1,\infty)\cup (-\infty,0] 的部分的值都该是无意义，为了方便起见，我们设这个值为 \infty。

于是，每一次平移之后，凸包非 \infty 的部分总是被限制。很容易地，我们知道对第 i 个凸包而言，这个限制的范围是 [(i-1)\cdot p+1,mx]，也即 b_i\in [(i-1)\cdot p+1,mx]。这意味着这个凸包在平移拉伸后，还多了个截取的过程。而加入一个 |x-a_i|，这都是 \mathrm{slope\ trick} 的基础套路，用两个懒标记和堆来维护分界点即可。而由于新增的截取过程，这让我们在往堆里加分界点的时候，可以与 mx 取 \min。

于是就剩下构造答案了，首先得知道三个性质。

性质一：我们在维护这个凸包的时候，除了维护每个斜率变化的分界点外，还维护了最低点的纵坐标值。于是在最后的凸包里，我们知道 b_n 一定处于凸包的最小值所在的横坐标区间中。但要注意到，对此时的凸包而言，最低点不一定是斜率为零的点了，这是由于多了截取的存在。

性质二：我们要清晰知道一件事，在 \mathrm{slope\ trick} 中，第 i 个凸包一定是前 i 个数构成的答案凸包。这是什么概念呢？这意味着在这个凸包上的所有值一定是合法的，也即一定有一个对应的解。这个利用归纳法是容易证明，也不再赘述。既然凸包上的值一定合法，也就意味着无论最后一个数如何取，只要是在凸包上，意味着一定有一组解来对应它。

性质三：我们要知道一个显然的贪心性质，在前面的凸包中，如果每次 b_i 都能取到凸包最低点而且与后面不冲突的话，那就是一定不劣的。这个是容易感受出来的，若斜率为零的那一段能够恒久存在，那我们一直选择这一段是永远不劣的。

有了以上的三个性质，我们就可以构造答案了。

性质三意味着在初步构造中，我们可以贪心地让每个 b_i 成为当前凸包的最低点。然后利用性质二，我们知道 b_n 一定是合法的，所以进行倒推，使得每个 b_i\in [b_{i+1}-q,b_{i+1}-p]。那么如何倒推呢？若初步构造的 b_i 已经在这个区间了，那就皆大欢喜。若 b_i<b_{i+1}-q，由于一定存在一组解，利用贪心的性质，此刻让 b_i\leftarrow b_{i+1}-q 一定最优，原因也很简单，因为初步构造时 b_i 是凸包的最低点，而此时 b_i 离 b_{i+1}-q 最近，那么取这个端点一定最优。大于右端点同理。

于是就顺利构造出一组答案了，且一定是最小的(因为 b_n 一定在最终凸包上)。

代码实现上，我们不一定要真的对维护分界点的堆进行即时的截取。可以类似懒标记那样，对每个初步构造的 b_i 先与 mx 取 \min，再与 (i-1)\cdot p+1 取 \max 即可。这样代码会比较好写。

同时在这里也给出了所有 \mathrm{slope\ trick} 题的答案构造方式。


//2022.8.30 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN {
    int n,mx,p,q;
    int a[N];
    LL b[N];
    priority_queue<LL> L;
    priority_queue<LL,vector<LL>,greater<>> R;
    inline void MAIN(const int &Case) {
        n=read(),mx=read(),p=read(),q=read();
        for(int i=1;i<=n;i++)a[i]=read();
        LL tagl=0,tagr=0;
        L.push(a[1]),R.push(a[1]),b[1]=a[1];
        for(int i=2;i<=n;i++){
            tagl+=p,tagr+=q;
            LL l=L.top()+tagl,r=R.top()+tagr;
            if(a[i]<l)L.pop(),R.push(l-tagr),L.push(a[i]-tagl),L.push(a[i]-tagl);
            else if(a[i]>r)R.pop(),L.push(r-tagl),R.push(a[i]-tagr),R.push(a[i]-tagr);
            else L.push(a[i]-tagl),R.push(a[i]-tagr);
            LL t=L.top()+tagl;
            b[i]=min((LL)mx,max((LL)p*(i-1)+1,t));
        }
        for(int i=n-1;i>=1;i--){
            if(b[i]>b[i+1]-p)b[i]=b[i+1]-p;
            if(b[i]<b[i+1]-q)b[i]=b[i+1]-q;
        }
        LL ans=0;
        for(int i=1;i<=n;i++)ans+=abs(a[i]-b[i]);
        printf("%lld\n",ans);
    }
}