题目地址：Codeforces：Problem – 5E – Codeforces、洛谷：CF5E Bindian Signalizing – 洛谷 | 计算机科学教育新生态

题目描述

Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by n hills, forming a circle. On each hill there was a watchman, who watched the neighbourhood day and night.

In case of any danger the watchman could make a fire on the hill. One watchman could see the signal of another watchman, if on the circle arc connecting the two hills there was no hill higher than any of the two. As for any two hills there are two different circle arcs connecting them, the signal was seen if the above mentioned condition was satisfied on at least one of the arcs. For example, for any two neighbouring watchmen it is true that the signal of one will be seen by the other.

An important characteristics of this watch system was the amount of pairs of watchmen able to see each other’s signals. You are to find this amount by the given heights of the hills.

题意简述

有$n$座山头形成环状，每个山头的高度已知。两个山头能互相看到定义为两个山头把环切成的两段圆弧（不含端点），至少一段中不含比它们还高的山。求这些山头中能互相看到的山头的对数。

输入输出格式

输入格式：
The first line of the input data contains an integer number n (3 ≤ n ≤ 10^6), n — the amount of hills around the capital. The second line contains n numbers — heights of the hills in clockwise order. All height numbers are integer and lie between 1 and 10^9.

输出格式：
Print the required amount of pairs.

输入输出样例

输入样例#1：

5
1 2 4 5 3

输出样例#1：

7

题解

参考资料：CF5E Bindian Signalizing – Home – 洛谷博客
能互相看到的山头有一高一低和两个高度相等的情况，我们考虑枚举低的山头，来计算出高的山头或高度相等的山头，根据数据范围，计算的复杂度应该不高于$O(\log n)$。
接下来是怎么算的问题，对于一座山头，有向左和向右两种选择，且每个方向上能看到的比它高的山头不超过1个，即距离它最近还比它高的那个山头。在这个山头之后的山头，都会因为这个山头挡住了低山头而无法看到。计算出一个点向左向右距离最近且高度大于它的位置，可以通过动态规划的思想解决。以计算向左看最近高度大于第$i$座山头为例，令$l(i)$表示上述量，从左到右枚举$i$，初始化$l(i)=i-1$，若$l(i)$不满足高度条件，就$l(i)=l(l(i))$后再次检查，循环进行上述过程，直到满足高度条件。向右看时只需将枚举方向倒过来就可以了。
另外还需要考虑高度相等的山头，由于不能重算，我们固定向右找与第$i$座山头相同高度的山，设为$cnt(i)$，能看得见的高度相同的山一定在区间$[i, r(i)]$中，在计算$r(i)$时将高度条件设置为大于等于，循环停止时，$r(i)$若与$i$高度相等，则可以通过$cnt(i)=cnt(r(i))+1$计算出$cnt(i)$。最后再用$r(i)=r(r(i))$多跳一步，就可以找到严格大于的山头了。
对于山头$i$，它能看到的山头有$l(i)$、$r(i)$两座比它高的，还有$cnt(i)$座与它高度相等的，都会对答案产生贡献。
为了方便处理，我们断环为链的时候，将环中最高的山作为断点，且将链的首尾都设置为这座山，这样就可以减少边界情况的特殊处理。由于实际上是一个环，需要判断一下$l(i)$和$r(i)$是否是同一座山。以及，所有最高的山都不会对答案产生贡献。
预处理$l(i), r(i), cnt(i)$复杂度$O(n)$（未证明，脑补出来的），计算答案复杂度$O(n)$，总复杂度$O(n)$。

代码

// Code by KSkun, 2019/7
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], * p1 = buf, * p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 1000005;

int n, a[MAXN], b[MAXN], l[MAXN], r[MAXN], cnt[MAXN];

int main() {
    n = readint();
    int mx = 0;
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        if(a[i] > a[mx]) mx = i;
    }
    for(int i = 1; i <= n; i++) {
        b[i] = a[(mx + i - 2) % n + 1];
    }
    b[n + 1] = b[1];
    for(int i = 1; i <= n; i++) {
        l[i] = i - 1;
        while(l[i] && b[l[i]] <= b[i]) {
            l[i] = l[l[i]];
        }
    }
    for(int i = n; i >= 1; i--) {
        r[i] = i + 1;
        while(r[i] <= n && b[r[i]] < b[i]) {
            r[i] = r[r[i]];
        }
        if(r[i] <= n && b[i] == b[r[i]]) {
            cnt[i] = cnt[r[i]] + 1;
            r[i] = r[r[i]];
        }
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += cnt[i];
        if(b[i] < b[1]) {
            if(l[i] == 1 && r[i] == n + 1) ans++;
            else ans += 2;
        }
    }
    printf("%lld", ans);
    return 0;
}