CF5E Bindian Signalizing

tony102

2021 年 09 月 24 日

1385 次浏览

1 条评论

834字数

题解

[Link](https://www.luogu.com.cn/problem/CF5E)

[51nod 1482](https://www.51nod.com/Challenge/Problem.html#problemId=1482)

## Sol

首先断环成链。

我有一个很 naive 的做法，通过双指针，建立线段树，每次挪动左右指针时询问当前区间的最大值是否 $\leq$ 左右指针的高度，统计答案。

这样过不去 $n \leq 3 \times 10^6$ 的数据。但是发现，用线段树查这个最小值这个操作非常愚蠢。

最高的山无论如何都会挡住别的山。我们以最高的山作为第一座山，其余的山按照原顺序排列。因为最高的山不会有除了相邻的不会有任何中间还有跨度的两座山对答案有贡献。

我们设 $l_i$ 表示往左第一个比 $i$ 高的位置，$r_i$ 即往右同理的位置。那么就有 $(i,l_i)$ 和 $(i, r_i)$ 两组。注意在 $(l_i, r_i]$ 这个区间中与 $i$ 高度相等的山也要给答案贡献。

求 $l_i$ 和 $r_i$ 可以用一个单调栈来实现，最后因为顺时针和逆时针都可以统计答案，断环成链之后相当于正着做一遍反着做一遍就行了。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 3e6 + 5;

int n, m;
int a[SIZE], b[SIZE], sta[SIZE], l[SIZE], r[SIZE], tag[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int main() {
    n = read(); int mx = 0;
    for (int i = 1; i <= n; ++ i) {
        a[i] = read();
        if (a[mx] < a[i]) mx = i;
    }
    for (int i = mx; i <= n; ++ i) b[++ m] = a[i];
    for (int i = 1; i < mx; ++ i) b[++ m] = a[i];
    int top = 0;
    for (int i = 2; i <= n; ++ i) {
        while (top && b[i] >= b[sta[top]]) -- top;
        l[i] = sta[top], sta[++ top] = i;
    }
    sta[top = 0] = n + 1;
    for (int i = n; i >= 2; -- i) {
        while (top && b[i] >= b[sta[top]]) {
            if (b[i] == b[sta[top]]) tag[i] = tag[sta[top]] + 1;
            -- top;
        }
        r[i] = sta[top], sta[++ top] = i;
    }
    LL ans = 0; mx = 0;
    for (int i = 2; i <= n; ++ i) {
        if (l[i] > 0) ++ ans;
        if (r[i] <= n) ++ ans;
        ans += tag[i];
    }
    memset(tag, 0, sizeof(tag));
    for (int i = 2; i <= n; ++ i) {
        if (b[i] >= mx) tag[i] = 1;
        mx = std::max(mx, b[i]);
    }
    mx = 0;
    for (int i = n; i >= 2; -- i) {
        if (b[i] >= mx) tag[i] = 1;
        mx = std::max(mx, b[i]);
    }
    for (int i = 2; i <= n; ++ i) ans += tag[i];
    printf("%lld\n", ans);
    return 0;
}
```

最后修改：2021 年 09 月 24 日