以找到 L 为例。设 \mathrm {ask}(x,i) 为 [x,i] 这个区间的最小值(x\le i),发现 \mathrm {ask}(x,i) 单调不降,考虑从 i 往左边二分查找。如果 \mathrm {ask}(mid,i)<a_i,就让 l=mid+1,否则让 r=mid。
找到 R 是同理的。然后就做完了。
时间复杂度 \mathcal O(n\log n)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, f[N][22], ans;
int ask (int l, int r) { // 返回 [l,r] 的最小值
int s = __lg (r - l + 1);
return min (f[l][s], f[r - (1 << s) + 1][s]);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
memset (f, 0x3f, sizeof f);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i][0];
for (int j = 1; j <= 19; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (int i = 1; i <= n; i++) {
int l = 1, r = i, L, R;
while (l < r) { // 向左查找
int mid = (l + r) >> 1;
if (ask (mid, i) == f[i][0]) r = mid;
else l = mid + 1;
}
L = l, l = i, r = n;
while (l < r) { // 向右查找
int mid = (l + r + 1) >> 1;
if (ask (i, mid) == f[i][0]) l = mid;
else r = mid - 1;
}
R = l;
ans += f[i][0] * (i - L + 1) * (R - i + 1); // 累加贡献
}
cout << ans;
return 0;
}
首先 [l,r] 可以简单地从 i 往两边二分找到,可以参照 AGC005B 的方法。根据定义,a_{l-1} > a_i,所以 L 可以通过在 [1,l-2] 上二分得到。具体地,需要找到 [1,l-2] 这个区间中从右边数第一个大于 a_i 的数。设 \mathrm {ask}(x,y) 为 [x,y] 这个区间的最大值(x\le y),考虑从 y 往左边二分查找。如果 \mathrm {ask}(mid,y)<a_i,就让 r=mid,否则让 l=mid+1。
区间最大值由 ST 表维护即可,时间复杂度 $\mathcal O(n\log n)$。
代码中细节还是挺多的,调不过的可以对比一下。
```cpp
// 为了看着方便,在每一次二分后空了一行
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, f[N][22], ans;
int ask (int l, int r) {
int s = __lg (r - l + 1);
return max (f[l][s], f[r - (1 << s) + 1][s]);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i][0];
for (int j = 1; j <= 19; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (int i = 1; i <= n; i++) {
int l = 1, r = i, L, R, l1, r1;
while (l < r) {
int mid = (l + r) >> 1;
if (ask (mid, i) == f[i][0]) r = mid;
else l = mid + 1;
}
l1 = l;
l = 1, r = max (1ll, l1 - 2);
while (l < r) {
int mid = (l + r) >> 1;
if (ask (mid, max (mid, l1 - 2)) < f[i][0]) r = mid;
else l = mid + 1;
}
if (f[r][0] > f[i][0] && f[r + 1][0] > f[i][0]) L = r + 1;
else L = r;
l = i, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ask (i, mid) == f[i][0]) l = mid;
else r = mid - 1;
}
r1 = l;
R = l;
ans += f[i][0] * (l1 - L) * (R - i + 1);
// 左边第二大,右边第一大
l = min (n, r1 + 2), r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ask (min (mid, r1 + 2), mid) < f[i][0]) l = mid;
else r = mid - 1;
}
if (f[l][0] > f[i][0] && f[l - 1][0] > f[i][0]) R = l - 1;
else R = l;
ans += f[i][0] * (i - l1 + 1) * (R - r1);
// 左边第一大,右边第二大
}
cout << ans;
return 0;
}
```
大家对文章有什么好的建议欢迎在下面评论,有相关题目也可以提供,我会在修改时添加上贡献者,谢谢!