牛客练习赛66 E

牛客练习赛66 E

传送门

题意：给你一个排列，问有多少个区间满足第一个数字是次小值，最后一个值是次大值。

分析：考虑到次小值的约束，可行的右端点肯定是一个区间。即第一个小于它的值到第二个小于它的值(不包含)之间的所有位置。同理可以考虑次大值的约束。最终对于一个右端点来说，可行的左端点肯定也是一个区间值。现在考虑暴力枚举左端点，这个时候要考虑可行的右区间内，有多少个右端点可行的左区间是包含自己这个左端点的。这么暴力更新肯定是不行的。注意到一个左端点会对固定右区间的元素造成贡献，所以可以用两个端点的插入删除来代替这一个行为。并且在考虑到一个右端点时，考虑其可行区间内的区间和即可，这可以用一个BIT维护。

#include<bits/stdc++.h>

#define PB push_back
#define MP make_pair
#define fi first
#define se second

using namespace std;

typedef pair<int,int> PII;

typedef long long LL;

inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){res*=10;res+=ch-'0';ch=getchar();}

    return res*f;
}

const int N = 1000005;

int a[N], n, p[N][2], s[N][2];

int mx[N][21], mn[N][21];

int lg[N];

vector<PII> G[N];


struct fwk{
    int T[N];

    inline int lowbit(int x){return x&-x;}

    void add(int x, int v){
        while(x<=n){
            T[x]+=v;
            x+=lowbit(x);
        }
    }

    int getSum(int p){
        int res=0;
        while(p){
            res+=T[p];
            p-=lowbit(p);
        }

        return res;
    }

    int getSum(int l, int r){
        return getSum(r)-getSum(l-1);
    }

};

fwk bit;

inline int askMin(int l, int r){
    int id=lg[r-l+1];
    return min(mn[l][id],mn[r-(1<<id)+1][id]);
}

inline int askMax(int l, int r){
    int id=lg[r-l+1];
    return max(mx[l][id],mx[r-(1<<id)+1][id]);
}

void get_pre(){
    for(int i=1;i<=n;++i){
        int l=i;
        for(int id=20;id>=0;--id){
           int tr=l+(1<<id);
           if(tr<=n&&askMin(i,tr)==a[i])l+=(1<<id);
        }
        if(l==n){
            p[i][0]=p[i][1]=-1;
            continue;
        }
        ++l;p[i][0]=l;
        int r=l;
        for(int id=20;id>=0;--id){
            int tr=r+(1<<id);
            if(tr<=n&&askMin(l+1,tr)>a[i])r+=(1<<id);
        }
        p[i][1]=r;
    }
}

void get_suf(){
    for(int i=1;i<=n;++i){
        int r=i;
        for(int id=20;id>=0;--id){
            int tl=r-(1<<id);
            if(tl>=1&&askMax(tl,i)==a[i])r-=(1<<id);
        }
        if(r==1){
            s[i][0]=s[i][1]=-1;
            continue;
        }
        --r;
        s[i][1]=r;

        int l=r;
        for(int id=20;id>=0;--id){
            int tl=l-(1<<id);
            if(tl>=1&&askMax(tl,r-1)<a[i])l-=(1<<id);
        }

        s[i][0]=l;
    }
}


int main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();

    for(int i=1;i<=n;++i)mx[i][0]=mn[i][0]=a[i];

    for(int id=1;id<=20;++id){
        for(int i=1;i+(1<<id)-1<=n;++i){
            mx[i][id]=max(mx[i][id-1],mx[i+(1<<id-1)][id-1]);
            mn[i][id]=min(mn[i][id-1],mn[i+(1<<id-1)][id-1]);
        }
    }


    lg[1]=0;
    for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

    get_pre();get_suf();

    LL ans=0;

    for(int i=1;i<=n;++i){
        if(p[i][0]==-1||p[i][1]==-1)continue;
        G[p[i][0]].PB(MP(i,1));
        G[p[i][1]+1].PB(MP(i,-1));
    }

    for(int i=1;i<=n;++i){
        for(auto it:G[i]){
            bit.add(it.fi,it.se);
        }
        if(s[i][0]==-1||s[i][1]==-1)continue;
        ans+=bit.getSum(s[i][0],s[i][1]);
    }

    printf("%lld",ans);


    return 0;
}