题目描述

宅邸迅速的燃烧着，必须带贝蒂走出禁书库！凭着感觉，又一次直接找到禁书库的门。

“你，是那个人嘛？”400年了，当初圣域建立结界时没有进入圣域，被伤了心的人工精灵贝蒂，与强欲魔女签订契约，守护宅邸的禁书库，直至“那个人”的到来，那个人会解开贝蒂的心结。

“我不是那个什么人，但我会成为你唯一的人。我会给你幸福!”

精灵与人签订契约，从此相依为命。这便是，永恒的契约。

宅邸里，罗兹瓦尔的房间图书柜后，有一条链接宅邸和圣域的秘密通道，其中有一个神奇的大回环，由n块石头组成。

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

被罗兹瓦尔雇佣的猎肠者躲在这秘密的通道中，为了能够更好的观察通道中的情况，她想知道有多少对石头能够互相看到。

数据范围

40%，n<=200

60%，n<=2000

70%，n<=100000

80%，n<=1000000,1<=ai<=1000000

100%，n<=1000000，T<=5，1<=ai<=1000000000

解法

单调栈。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="forever.in";

const char* fout="forever.out";

const ll inf=0x7fffffff;

const ll maxn=1000007;

ll t,n,i,j,k,ans,maxx,mxid;

ll a[maxn];

ll read(){

    char ch=getchar();

    ll x=0;

    while (ch<'0' || ch>'9') ch=getchar();

    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    return x;

}

struct stack{

    ll a[maxn],c[maxn];

    void init(){

        memset(a,0,sizeof(a));

        memset(c,0,sizeof(c));

    }

    stack(){

        init();

    }

    void push(ll v){

        ll k=0;

        while (a[0] && v>a[a[0]]){

            ans+=c[a[0]];

            c[0]-=c[a[0]];

            c[a[0]--]=0;

        }

        if (!a[0] || a[a[0]]!=v) a[++a[0]]=v;

        c[a[0]]++;

        c[0]++;

        ans+=c[a[0]]-1;

        if (a[0]>=2) ans++;

    }

    void fin(){

        while (a[0]>=2 && c[1]>=2 || a[0]>=3){

            c[0]-=c[a[0]];

            ans+=c[a[0]--];

        }

    }

}S;

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    t=read();

    while (t--){

        n=read();

        ans=0;

        maxx=0;

        S.init();

        for (i=1;i<=n;i++){

            a[i]=read();

            if (a[i]>maxx){

                maxx=a[i];

                mxid=i;

            }

        }

        S.push(maxx);

        for (i=mxid%n+1;i!=mxid;i=(i+1>n?1:1+i)){

            S.push(a[i]);

        }

        S.fin();

        printf("%lld\n",ans);

    }

    return 0;

}