AT_abc234_g [ABC234G] Divide a Sequence

思路

定义 dpidp_i 表示将前 ii 个分为若干段的价值总和。容易得到状态转移方程:

dpi=j=1i1dpj×(maxk=j+1i{ak}mink=j+1i{ak}) dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\})}

于是考虑将其拆成 maxk=j+1i{ak}\max_{k = j + 1}^{i}\{a_k\}mink=j+1i{ak}\min_{k = j + 1}^{i}\{a_k\} 两个子问题。

在这里我们先讨论 maxk=j+1i{ak}\max_{k = j + 1}^{i}\{a_k\} 这一子问题。

xx 表示在 ii 左边第一个大于 aia_i 的位置。那么,一定有 maxk=x+1i{ak}=ai\max_{k = x + 1}^{i}\{a_k\} = a_imaxk=1x{ak}>ai\max_{k = 1}^{x}\{a_k\} > a_i

所以,aia_i 能对答案产生贡献当且仅当 j>xj > xxx 是很好求的,直接用单调栈维护即可。

那么我们现在的问题就变为了如何求 jxj \leq x 所能产生的贡献。

考虑用一个数组 mximx_i 表示 j=1i1dpj×maxk=j+1i{ak}\sum_{j = 1}^{i - 1}{dp_j \times \max_{k = j + 1}^{i}\{a_k\}}

那么显然有:

mxi=mxx+(k=xi1dpk)×ai mx_i = mx_x + (\sum_{k = x}^{i - 1}dp_k) \times a_i

然后用前缀和优化一下即可做到 Θ(n)\Theta(n) 时间复杂度解决。

对于 mink=j+1i{ak}\min_{k = j + 1}^{i}\{a_k\} 的子问题同理可用一个 mnmn 数组解决。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>  
#define re register
#define int long long

using namespace std;

const int N = 3e5 + 10,mod = 998244353;
int n;
int arr[N];
int tp1,st1[N];
int tp2,st2[N];
int Max[N],Min[N],dp[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;
}

inline int Add(int a,int b){
return (a + b) % mod;
}

inline int Sub(int a,int b){
return ((a - b) % mod + mod) % mod;
}

inline int Mul(int a,int b){
return a * b % mod;
}

signed main(){
dp[0] = 1;
n = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
for (re int i = 1;i <= n;i++){
while (tp1 && arr[st1[tp1]] <= arr[i]) tp1--;
while (tp2 && arr[st2[tp2]] >= arr[i]) tp2--;
if (tp1) Max[i] = Add(Max[st1[tp1]],Mul(Sub(dp[i - 1],dp[st1[tp1] - 1]),arr[i]));
else Max[i] = Mul(dp[i - 1],arr[i]);//当 tp1 和 tp2 为 0 时需要特殊处理,避免越界
if (tp2) Min[i] = Add(Min[st2[tp2]],Mul(Sub(dp[i - 1],dp[st2[tp2] - 1]),arr[i]));
else Min[i] = Mul(dp[i - 1],arr[i]);
dp[i] = Add(dp[i - 1],Sub(Max[i],Min[i]));
st1[++tp1] = st2[++tp2] = i;
}
printf("%lld",Sub(dp[n],dp[n - 1]));
return 0;
}

AT_abc234_g [ABC234G] Divide a Sequence
http://watersun.top/[题解]AT_abc234_g [ABC234G] Divide a Sequence/
作者
WaterSun
发布于
2024年6月12日
许可协议