题目描述
题目描述：
给出一个 n 个数的序列，一个区间的价值是区间内最小值乘最大值的 积。求所有区间价值和。答案对 998244353 取模。
样例输入：
5 4 2 3 1 5
样例输出：
107
数据范围：
$n\le 5*10^5,a_i\le 10^9$
Solution
我们考虑分治，然后这时候我们注意到左边的后缀和右边的前缀的 $max$ 以及 $min$ 都是单调的
然后我们枚举左端点，然后找到最靠右的右边的前缀 $max$ 小于等于左边区间的 $max$ 的位置 $pm$
同理找到最靠右的右边的前缀 $min$ 大于等于左边区间的 $min$ 的位置 $pn$
那么对于右端点在 $[m+1,min\lbrace pn,pm\rbrace]$，区间最大和最小值都是在左边，可以直接计算答案
右端点在 $[min\lbrace pn,pm\rbrace+1,max\lbrace pn,pm\rbrace]$，区间最大或者最小在左边，另一个在右边，可以预处理得到答案
右端点在 $[\lbrace pn,pm\rbrace+1,r]$，最大和最小值都在右边，可以预处理得到答案
时间复杂度 $O(n\log n)$
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
| #include <iostream>
#include <cstdio>
#define maxn 500010
#define ll long long
#define INF 1000000000
using namespace std;
const int p = 998244353;
int n, a[maxn];
ll ans;
int mn[maxn], mx[maxn]; ll v[maxn], vn[maxn], vm[maxn];
void solve(int l, int r) {
if (l == r) return (void) (ans = (ans + (ll) a[l] * a[l]) % p);
int m = l + r >> 1, pn = m, pm = m; ll Min = INF, Max = -INF;
mn[m] = INF; mx[m] = -INF; v[m] = vn[m] = vm[m] = 0;
for (int i = m + 1; i <= r; ++i) {
mn[i] = min(mn[i - 1], a[i]);
mx[i] = max(mx[i - 1], a[i]);
v[i] = (v[i - 1] + (ll) mx[i] * mn[i]) % p;
vn[i] = (vn[i - 1] + mn[i]) % p;
vm[i] = (vm[i - 1] + mx[i]) % p;
}
for (int i = m; i >= l; --i) {
Min = min(Min, (ll) a[i]);
Max = max(Max, (ll) a[i]);
while (pn < r && mn[pn + 1] >= Min) ++pn;
while (pm < r && mx[pm + 1] <= Max) ++pm;
ans = (ans + Min * Max % p * (min(pn, pm) - m)) % p;
if (pn < pm)
ans = (ans + (vn[pm] - vn[pn]) * Max) % p;
else if (pm < pn)
ans = (ans + (vm[pn] - vm[pm]) * Min) % p;
ans = (ans + v[r] - v[max(pn, pm)]) % p;
}
solve(l, m); solve(m + 1, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
solve(1, n); cout << (ans + p) % p << "\n";
return 0;
}
|