P8067 题解

songhongyi · 2023-12-20 20:11:53 · 题解

随机题目启动。

设 c 的前缀和为 s_i。

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

对于固定的 r，考虑两个操作位置 l'<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;
}