Bindian Signalizing

这是 2010 年 Codeforces Beta Round #5 中的 E 题，曾在 2017 年京东笔试中出现，转载本题解请注明出处

题目大意

由 $n$ 座山峰构成的环形山脉，第 $i$ 座山峰的高度为 $h_i$，每座山峰设有一个瞭望台，请你计算能互相瞭望的山峰对数。两座山峰能互相瞭望的含义是，中间没有更高山峰

思路分析

对于任意一座山峰，与它能互相瞭望的最右端点一定是右侧最近且更高的山。我们想到单调栈可在 $O(n)$ 时间求出 $n$ 个数中每个数右侧最近且更大的数

维护一个严格单调递减栈，仅当遇到更大元素时，栈顶才需出栈，此时新元素是出栈元素右侧最近且更大的数。我们发现，栈顶出栈时，它已遇到能与其互相瞭望的最右端点。换句话说，从入栈到出栈间遇到的所有数便是右侧能与其互相瞭望的所有山峰。由于每个元素只出入栈一次，只要统计在此期间它们遇到的所有右端点，即可不重不漏算出答案

但进一步思考，由于山是环形，一直向右能回到自己左侧，而左侧已经把自己当成过右端点，这将导致重复解，必须找出这种情况发生的条件，并特殊处理。根据题意，只有中间无更高山峰时，两端才能互相瞭望，如果一直向右能跨越最高峰，就代表两端和最高峰等高。找到情况发生的条件后，考虑如何避免重复解，我们约定，和最高峰等高的山，只作为前面最高峰的右端点

实现细节

根据以上分析，我们首先需要知道最高峰高度，也需要判断前面是否遍历过最高峰。那么，不妨把某座最高峰当作起点，从它右侧下一座开始顺时针遍历，直到再次遇到该座最高峰时停止。由于是单调递减栈，这也意味着遍历过程不用判断栈空

由于可能存在高度相同山峰，把键值对 $(value，count)$ 作为栈内元素类型，表示有 $count$ 座高度为 $value$ 的山峰。当有新元素入栈时

栈顶小于新元素，需要出栈顶。由于新元素是栈顶右侧最近且更大的数，即新元素是栈顶能与其互相瞭望的最右端点，更右侧的山都不能与其互相瞭望，所以出栈后栈顶右侧山峰已统计完。由于栈顶可能包含多座高度相同山峰，新元素是它们共同的最右端点，所以答案加上栈顶 $count$
直到栈顶不小于新元素
1. 栈顶等于新元素，新元素入栈，即令栈顶 $count$ 加一。在此之前，由于新元素与栈顶等高，能够作为栈顶右端点，所以答案加上栈顶 $count$。其次，如果栈顶下侧还存在一个元素，答案加一，因为下侧更高，新元素能作为它的右端点，又因为它阻挡了更左山峰，所以更下侧元素无需考虑
2. 栈顶大于新元素，直接入栈。在此之前，由于它能作为栈顶右端点，所以答案加一。由于 $2.a$ 中的相同原因，栈顶以下元素无需考虑

所有元素都入栈一次后，如果栈不空，继续出栈。由单调栈性质，之所以栈内还剩余元素，是因为它们右侧都不存在比它们大的数，由此推出，最高峰是能与它们互相瞭望的最右端点

剩余三个以上元素。栈顶向右看能与最高峰互相瞭望，答案要加 $top.count$，出栈后它的右侧端点已统计完
直到剩余两个元素
1. 最高峰只有一座。虽然栈顶向右能找到最高峰与其互相瞭望，但 $TOP$ 中所有元素在入栈时，最高峰已把它们当成过右端点，见入栈分析 $2.a,\ 2.b$，此时不能重复统计
2. 最高峰不止一座。栈顶向右能找到栈底第一座最高峰，因此答案要加上 $top.count$，出栈后其右侧端点已统计完
直到剩余一个元素，它一定是最高峰，无论有多少座，根据约定，后入栈的都已作为先入栈的右端点，见思路分析末段，因此不再重复统计

总结：计数类问题一定要保证统计方式不重不漏，尤其关注边界情况。如果没有明显的划分标准，考虑先加再减或先减再加

#include <iostream>

#define V first
#define C second

using namespace std;
using LL = long long;

const int N = 1e6 + 5;
int tt = -1, a[N];
pair<int, int> s[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n, mx_i = 0; cin >> n;
    
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        if (a[i] > a[mx_i]) mx_i = i;
    }
    
    LL ans = 0;
    s[++ tt] = {a[mx_i], 1};
    for (int i = mx_i + 1; i != mx_i; i = (i + 1) % n) {
        while (a[i] > s[tt].V) ans += s[tt --].C;
        if (a[i] == s[tt].V) ans += s[tt].C ++ + !!tt;
        else ans ++, s[++ tt] = {a[i], 1};
    }
    
    while (tt --) if (tt || s[0].C > 1) ans += s[tt + 1].C;

    cout << ans << '\n';

    return 0;
}

如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。

TG 大佬群 QQ 大佬群