题目链接
题目大意是，一个环上有n个点，当且仅当这两个点之间没有比这两个数中任意一个数大的数时，这两个点可以相互看见。求可以相互看见的点的对数。
思路： 遇到环的问题我们一般都是把环拆成链，但是这里如果只是简单的把数组复制一遍的话，我们发现很难去重。环有一个特性就是可以循环移位，我们把最大的数放在最左边，这样的话从逆时针找，找到的最大的数的位置不可能大于1. 利用这个性质我们就可以写出这题。其实还是写了一上午，需要考虑很多细节。
我们用单调栈维护一个递减栈，重复的数我们不再重复的放入，而是用一个数组标记它出现的次数多了一次，当它要被弹出栈时，说明比它大的两个数都出现了（因为是递减栈，而最大的在第一个位置，并且最大的一定不会被弹出，所有在单调栈中这个数的上一个数一定比它大，而它被弹出也是因为出现了比它大的数，所以两个数都出现了）。那么这个数产生的贡献为（为了方便，我们设它的个数为 x x x） 2 ∗ x + ( x − 1 ) ∗ x / 2 2*x+(x-1)*x/2 2∗x+(x−1)∗x/2，即为比它大的两个数都可以连向他们，还有相等的数之间也可以任意连接。
一遍循环之后，单调栈里的数都是单调递减的了，我们一个一个的弹出来，它们能连向最大的数和它们的上一个数，所以也会产生两倍的个数的贡献。注意栈中的第二个数，如果第一个数只有一个的话，它只会产生一倍的贡献。因为它连的数是同一个。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const double Pi = acos(-1); namespace { template <typename T> inline void read(T &x) { x = 0; T f = 1;char s = getchar(); for(; !isdigit(s); s = getchar()) if(s == '-') f = -1; for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48); x *= f; } } #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define _srep(n,m,i)for (register int i = (n); i >= (m); i--) #define _sfor(n,m,i)for (register int i = (n); i > (m); i--) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) x & (-x) #define pii pair<int,int> #define fi first #define se second const int N = 1e6+5; int a[N], h[N], s[N], n, f[N]; void solve() { int top = 0; LL ans = 0; for(int i = 0; i < n; i++) { while(top && s[top] < h[i]) ans += 2 * f[top--]; // 这里我是分开写的，按照上面说的话可能一乘就爆int了，所以可以每增加一个就加一下，看下面的ans+= f[top]++; if(s[top] != h[i]) s[++top] = h[i], f[top] = 0; ans += f[top]++; } if(f[1] == 1 && top > 1) ans -= f[2]; while(top > 1) ans += 2 * f[top--]; cout << ans << endl; } int main() { int p = 1, top = 0; read(n); _for(0, n, i) read(a[i]), a[i] > a[p] && (p = i); _for(0, n, i) h[i] = a[(i+p)%n]; solve(); }