AT_abc263_d [ABC263D] Left Right Operation

思路

首先，不难发现最终的序列一定是形如下面的序列：

$$l,\dots,l,a_i,a_{i + 1},\dots,a_{i + j},r,\dots r$$

那么，我们就可以将其分为三段，每段都单独维护。

首先，对于第一段，我们可以枚举出最后一个 $l$ 的位置 $x$，那么和为 $x \times l$。

对于第二段显然可以用前缀和维护，但是有一个问题，我们还不知道这一段的末尾位置在哪里。换而言之，我们需要确定 $r$ 的起始位置。

那么，对于每一个位置 $i$，我们都可以 $\Theta(1)$ 查询出将 $i \sim n$ 全都修改为 $r$ 能够使序列变小多少，记作 $d_i$。

因此，我们可以用一个 pair 数组 $mx$ 维护 $d_i$ 的后缀最大值，那么 mx.fst 记录的是后缀最大值的值，ms.snd 记录的是后缀最大值的位置。

那么，要想使答案最小，我们在枚举 $i$ 时，就要是 $r$ 对答案的贡献小，即选择一个位置 $j$ 使得 $d_j$ 最大，那么，这个操作，我们可以直接使用 $mx$ 来查询。

最后所有求出的值，取 $\min$ 即可。

Code

#include <bits/stdc++.h>  
#define int long long  
#define fst first  
#define snd second  
#define re register  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const int N = 2e5 + 10,inf = 1e18 + 10;  
int n,x,y,ans = inf;  
int arr[N],sp[N],sn[N];//sp 为前缀和，sn 为后缀和   
pii mx[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
signed main(){  
    n = read();  
    x = read();  
    y = read();  
    for (re int i = 1;i <= n;i++){  
        arr[i] = read();  
        sp[i] = sp[i - 1] + arr[i];  
    }  
    for (re int i = n;i;i--) sn[i] = sn[i + 1] + arr[i];  
    mx[n + 1] = {0,n + 1};  
    for (re int i = n;i;i--){  
        int t = sn[i] - (n - i + 1) * y;  
        if (mx[i + 1].fst < t) mx[i] = {t,i};  
        else mx[i] = mx[i + 1];  
    }  
    for (re int i = 0;i <= n;i++){  
        int id = mx[i + 1].snd;  
        int sum = sp[id - 1] - sp[i] + i * x + (n - id + 1) * y;  
        ans = min(ans,sum);  
    }  
    printf("%lld",ans);  
    return 0;  
}