CF713C Sonya and Problem Wihtout a Legend

· · 题解

本篇题解复杂度为 O(n\log n)，并且同其他同复杂度题解不同的是，这里我用了维护凸壳来解释了这题（当然代码没啥不同）。本题解比较小白向，如果对凸包比较了解的话可以跳掉很多简单的证明。

主要和 codeforces 上的博客 有同样的思想。可能那里讲的稍微清晰一点。

首先我们将所有 a_i 减去 i 就可以从严格单调递增转化为单调不降，这样会方便很多。

然后考虑一个很简单的 DP。f(i,j) 表示只考虑前 i 个数，然后修改后的第 i 个数 \le j 的情况最小代价，g(i,j) 表示只考虑前 i 个数，然后修改后的第 i 个数 =j 的最小代价。我们发现 f 是 g 的前缀最小值，然后有转移 g(i,j)=f(i-1,j)+|a_i-j|。

到这里已经足矣完成 O(n^2) 的部分了。然而我们要继续优化后，必须考虑对状态进行优化。有经验的话可以很容易发现 f(i),g(i) 关于 j 具有凸性。一般来说这样就可以省掉一个维度。

具体怎么证明其实也很简单。对于一个 f(i)，我们把 f(i,j) 作为一个点 (j,f(i,j)) 画出来，然后相邻两个点连一下，就可以得到一个分段函数 F_i。我们对 g 做同样的操作得到 G_i。首先初始时两个必然都是凸函数。考虑转移。用归纳法，若 F_{i-1} 是凸的，则因为 |a_i-j| 是下凸的，F_{i-1} 也是凸的，两个凸函数相加得到的 G_{i} 也是凸的；然后 F_i 是 G_i 的前缀和，所以 F_i 也是凸的，所以可以得到每个 F 和 G 均为下凸壳。并且还有一个很好的性质，斜率均为整数（容易证明）。

然后是一个非常重要的维护手段——维护拐点来维护凸壳。一个下凸壳（其实上凸壳也是类似的）可以按照如下维护（维护一个集合和一条直线）：对于一个凸壳上的点 s_i，如果它两端的斜率不一样，就放拐点。设两边斜率差为 p，那就在集合中放入 p 个 s_i 的横坐标。由于最后一段必然是无限延申下去的一条支线，我们考虑用一个直线来描述一条直线。容易发现，用一个一次函数和一个拐点集合能够描述一个这样的斜率为整数的凸壳。

设凸函数 C_1,C_2 的集合为 S_1,S_2，并且直线分别为 f_1,f2，则 C=C_1+C_2 的集合为 S=S_1\cup S_2，一次函数是 f=f_1+f_2（斜率相加，截距相加）。

这道题有一个很好的地方，就是 F_i 的结尾的一次函数必然是一条水平的直线，G_i 的结尾的一次函数必然是一条斜率为 1 的直线，并且除了结尾部分 F_i 和 G_i 一样。所以我们可以通过移除一个集合内最大的拐点然后修改一下一次函数的斜率即可从 G_i 得到 F_i。

至于如何从 F_{i-1} 转移到 G_{i}，我们相当于加上一个凸函数 A_i(x)=|a_i-x|。首先 A_i(x) 的拐点集合应该为 \{a_i,a_i\}。考虑设 F_{i-1} 的最大的拐点为 s。

以上操作用一个堆就能维护了。

int n,ans,a;
priority_queue<int>q;

signed main() {
    n=read();
    rep(i,1,n) {
        q.push(a=read()-i);
        if(a<q.top()) q.push(a), ans+=q.top()-a, q.pop();
    }
    printf("%lld\n",ans);
    return 0;
}