E-骚区间

E-骚区间题解：这种题首先想到要枚举区间的一个右端点，然后统计有多少合法的左端点。然后我们来求以i作为右端点，左端点在 上时， 作为区间的次大值。那么我们就从左到右枚举右端点，要使 作为次大值，先找到之前出现的离他最近的比他大的数，再找到除了这个比他大的数之外离它最近的比他大的数，就用权值线段树，线段树上第i个位置记录在枚举到当前右端点为止满足 的k即可。同理还要维护以i作为左端点，右端点在 上时， 作为区间的次小值。同理从右往左枚举左端点，也用权值线段树维护即可。
最后统计答案，我们要统计的是对于i作为右端点，在 中有多少个左端点j满足 ，这个可以用线段树来解决，也就是在 处将线段树上j的位置+1，在 处将线段树上j的位置-1，最后只要枚举右端点i，求线段树在 上的区间和即可，时间复杂度

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const int N=1000005;

struct seg{
    int l,r;
    int mn,s,mx;
}t[N<<2];
int n;
ll ans;
int a[N],l1[N],r1[N],l2[N],r2[N];
vector<pair<int,int> > vec[N];

void update(int k){
    t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
    t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
    t[k].s=t[k<<1].s+t[k<<1|1].s;
}

void build(int k,int l,int r){
    t[k].l=l; t[k].r=r;
    t[k].mn=n+1; t[k].mx=0; t[k].s=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    update(k);
}

void modify_mx(int k,int p,int w){
    if (t[k].l==t[k].r){
        t[k].mx=w;
        return;
    }
    int mid=(t[k].l+t[k].r)>>1;
    if (p<=mid) modify_mx(k<<1,p,w);
    else modify_mx(k<<1|1,p,w);
    update(k);
}

int find_mx(int k,int L,int R){
    if (L>R) return 0;
    if (L<=t[k].l&&t[k].r<=R) return t[k].mx;
    int mid=(t[k].l+t[k].r)>>1;
    if (R<=mid) return find_mx(k<<1,L,R);
    if (L>mid) return find_mx(k<<1|1,L,R);
    return max(find_mx(k<<1,L,R),find_mx(k<<1|1,L,R));
}

int find_mn(int k,int L,int R){
    if (L>R) return n+1;
    if (L<=t[k].l&&t[k].r<=R) return t[k].mn;
    int mid=(t[k].l+t[k].r)>>1;
    if (R<=mid) return find_mn(k<<1,L,R);
    if (L>mid) return find_mn(k<<1|1,L,R);
    return min(find_mn(k<<1,L,R),find_mn(k<<1|1,L,R));
}

void modify_mn(int k,int p,int w){
    if (t[k].l==t[k].r){
        t[k].mn=w;
        return;
    }
    int mid=(t[k].l+t[k].r)>>1;
    if (p<=mid) modify_mn(k<<1,p,w);
    else modify_mn(k<<1|1,p,w);
    update(k);
}

void modify(int k,int p,int w){
    if (t[k].l==t[k].r){
        t[k].s+=w;
        return;
    }
    int mid=(t[k].l+t[k].r)>>1;
    if (p<=mid) modify(k<<1,p,w);
    else modify(k<<1|1,p,w);
    update(k);
}

int query(int k,int L,int R){
    if (L<=t[k].l&&t[k].r<=R) return t[k].s;
    int mid=(t[k].l+t[k].r)>>1;
    if (R<=mid) return query(k<<1,L,R);
    if (L>mid) return query(k<<1|1,L,R);
    return query(k<<1,L,R)+query(k<<1|1,L,R);
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    for (int i=1;i<=n;i++){
        if (a[i]<n){
            int p=find_mx(1,a[i]+1,n);
            if (p!=0){
                r1[i]=p;
                l1[i]=find_mx(1,a[p]+1,n)+1;
                l1[i]=max(l1[i],find_mx(1,a[i]+1,a[p]-1)+1);
            }
        }
        modify_mx(1,a[i],i);
    }
    build(1,1,n);
    for (int i=n;i>=1;i--){
        if (a[i]>1){
            int p=find_mn(1,1,a[i]-1);
            if (p!=n+1){
                l2[i]=p;
                r2[i]=find_mn(1,1,a[p]-1)-1;
                r2[i]=min(r2[i],find_mn(1,a[p]+1,a[i]-1)-1);
            }
        }
        modify_mn(1,a[i],i);
    }
    for (int i=1;i<=n;i++)
        if (l2[i]&&r2[i]){
            vec[l2[i]].push_back(make_pair(i,1));
            vec[r2[i]+1].push_back(make_pair(i,-1));
        }
    for (int i=1;i<=n;i++){
        for (int j=0;j<vec[i].size();j++) modify(1,vec[i][j].first,vec[i][j].second);
        if (l1[i]&&r1[i]) ans+=1ll*query(1,l1[i],r1[i]);
    }
    printf("%lld\n",ans);
    return 0;
}