题目大意

有一个神奇的大回环，由n块石头组成。
第i块石头有一个高度ai，两块不同的石头i,j能够互相看到，则它们在环上的两条路径中有至少一条路径上除了两个端点（即i,j）路径上石头高度都不大于min(ai,aj)。
求有多少对石头能够互相看到

数据范围n<=1e6，T<=5，1<=ai<=1e9

先不考虑ai=aj的情况

我们可以把序列加倍，然后用单调栈处理出l[i]和r[i]$(分别为i左右两边第一个满足a[j]比a[i]大的位置j)$,也就是只考虑i能看到a值比自己大的，同时如果i左右看到位置在原序列中相同ans只+1否则，这样就不会重复计算了。
ai=aj时，这个讨论起来不会很麻烦，处理l[i]的同时便可一起维护。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define ll long long
using namespace std;
const int maxn=2e6+5;
int i,j,n,m,t,a[maxn],l[maxn],r[maxn],f[maxn];ll ans,an[maxn];
void read(int &x){x=0;char c=getchar();while ((c<'0')||(c>'9')) c=getchar();while ((c>='0')&&(c<='9')) x=x*10+c-'0',c=getchar();
}
int main(){freopen("forever.in","r",stdin);freopen("forever.out","w",stdout);read(t);while (t>0){t--;read(n);fo(i,1,n+n) an[i]=0;fo(i,1,n) read(a[i]),f[i]=i;fo(i,n+1,n+n) a[i]=a[i-n];ans=0;fo(i,1,n+n) {j=i-1;while ((j>0)&&(a[j]<=a[i])) {if (a[j]==a[i]) {if (i<=n) f[i]=f[j],an[f[i]]++,ans+=an[f[i]];else{if (j<=n&&f[j]!=i-n) ans+=(ll)(an[f[j]]+1)*(an[f[i-n]]+1);}} j=l[j];}l[i]=j;}fod(i,n+n,1){j=i+1;while ((j<=(n+n))&&(a[j]<=a[i])) j=r[j];r[i]=j;}fo(i,1,n) if (r[i]<=n+n) ans++;fo(i,n+1,n+n) if (l[i]>0){if (r[i-n]!=l[i])ans++;}printf("%lld\n",ans);}
}