骚区间

%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17
分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.
求所有骚区间个数.容易想到枚举一个端点，求另外一个端点的有效个数，然后依次累加.
原序列定义为 .

• 对于当前下标为 的元素作为区间左端点 , 是下标大于 并且值小于 的下标最小的元素， 是下标大于 并且值小于 的下标最小元素。那么有效右端点一定是在 中.表示为：
  
  

• 对于当前下标为 的元素作为区间右端点 , 是下标小于 并且值大于 的下标最大的元素， 是下标小于 并且值大于 的下标最大元素。那么有效左端点一定是在中.用 表示。
  求解方法：
  1. set.
  2. 二分区间+ST表( 出题人题解方法,应该都知道,那我就鸽了 )

如果我们枚举右端点 ,已知左端点的有效区间范围，但是还要满足可取区间的元素的作为左端点时 在右端点的可取范围中.
那么我们可以将每个点 作为左端点时，右端点的可取范围 ,当 遍历到 位置时，对 位置加一，标记为有效点数，遍历到 ,对 位置减一，标记为无效点数。然后查询直接对 求一遍区间和即可。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x) 
using namespace std;

typedef long long ll;
const int maxn=1e6+10;

int sum[maxn];
void add( int x ,int c ) { while( x<maxn ) sum[x]+=c,x+=lowbit(x); }
int get_sum( int x ,int ans=0 ) { while(x) ans+=sum[x],x-=lowbit(x); return ans; }
int query( int l,int r ) { return get_sum(r)-get_sum(l-1); }

int sa[maxn],rev[maxn],ql[maxn],qr[maxn];
vector<int> inc[maxn],Dec[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for( int i=1;i<=n;i++ ) scanf("%d",sa+i);
    for( int i=1;i<=n;i++ ) rev[sa[i]]=i;
    set<int> S;
    for( int i=1;i<=n;i++ )
    {
        int id=rev[i];
        S.insert(id);
        auto v=S.upper_bound(id);
        if( v==S.end() ) continue;
        inc[*v].push_back(id);
        v++;
        if( v!=S.end() ) Dec[ (*v)-1 ].push_back(id);
    }
    S.clear();
    for( int i=n;i>=1;i-- )
    {
        int id=rev[i];
        S.insert(-id);
        auto v=S.upper_bound(-id);
        if( v==S.end() ) continue;
        qr[id]-=(*v);
        v++;
        if( v==S.end() ) ql[id]=1;
        else ql[id]-=(*v)-1;
    }    
    ll ans=0;
    for( int i=1;i<=n;i++ )
    {
        for( int v:inc[i] ) add(v,1);
        if( ql[i] && qr[i] ) ans+=query(ql[i],qr[i]);
        for( int v:Dec[i] ) add(v,-1);
    } 
    printf("%lld\n",ans);
}