自动搬运

查看原文

来自洛谷，原作者为

	songhongyi 懒

搬运于2025-08-24 22:35:39，当前版本为作者最后更新于2023-12-20 20:11:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

随机题目启动。

设 $c$ 的前缀和为 $s_i$。

先解决第一问。一次操作会将区间内全部变为右端点的值，则操作 $l\dots r$ 的收益是：

$$\left(r-l+1\right)\cdot c_r-\left(s_r-s_{l-1}\right) $$

对于固定的 $r$，考虑两个操作位置 $l'<l$，若 $l$ 更优，则：

$$\left(r-l+1\right)\cdot c_r-\left(s_r-s_{l-1}\right) \ge \left(r-l'+1\right)\cdot c_r-\left(s_r-s_{l'-1}\right) $$

转化为：

$$\left(l'-l\right)\cdot c_r \ge s_{l'-1}-s_{l-1}$$

即：

$$c_r \le\dfrac{s_{l-1}-s_{l'-1}}{l-l'}$$

这是一个斜率优化的形式。可以考虑 $n$ 个点 $(i,s_{i-1})$。其中在凸包内的点不可能成为最优位置，需要求出其凸包。在凸包上斜率单调，二分即可对每次的 $r$ 求出答案。

将序列翻转后再跑一遍第一问得到的结果就是第二问。

时间复杂度 $O(n \log n)$。

代码放一小段：

deque< int > q;
void solve()
{
    q.clear();
    for ( int i = 1; i <= n; i++ )
    {
        s[ i ] = s[ i - 1 ] + a[ i ];
    }
    q.push_back( 1 );
    int ans = -0x3f3f3f3f3f3f3f3f;
    for ( int i = 2; i <= n; i++ )
    {
        int p = q.front();
        int l = 1, r = q.size() - 1;
        while ( l <= r )
        {
            int mid = ( l + r ) / 2;
            if ( slope( q[ mid - 1 ], q[ mid ] ) >= a[ i ] )
            {
                p = q[ mid ];
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        ans = max( ans, s[ n ] + a[ i ] * ( i - p + 1 ) - ( s[ i ] - s[ p - 1 ] ) );
        while ( q.size() >= 2 and slope( q[ q.size() - 1 ], q[ q.size() - 2 ] ) <= slope( q[ q.size() - 1 ], i ) )
        {
            q.pop_back();
        }
        q.push_back( i );
    }
    cout << ans << endl;
}