子串

不会数据结构的人去理解真ri gou

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,sum[N];
int lowbit(int x)
{
    return x&(-x);
}
struct vv{
    int l,r;
};

vector<vv>W[N];
vector<int>L[N],R[N];
int ask(int pos)
{
    int res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}

void insert(int pos,int val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}
int a[N];
long long ans=0;
int lmi[N],rmi[N],lmx[N],rmx[N],st[N],top=0;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)//处理lmi
    {
        while(top&&a[st[top]]>a[i]) top--;
        lmi[i]=top?st[top]+1:1;st[++top]=i;//维护递增序列.
    }
    top=0;
    for(int i=n;i>=1;i--)//处理rmi
    {
        while(top&&a[st[top]]>a[i]) top--;
        rmi[i]=top?st[top]-1:n;st[++top]=i;//维护.
    }
    top=0;
    for(int i=1;i<=n;i++)//处理lmx
    {
        while(top&&a[st[top]]<a[i]) top--;
        lmx[i]=top?st[top]+1:1;st[++top]=i;//维护递增序列.
    }
    top=0;
    for(int i=n;i>=1;i--)//处理rmx
    {
        while(top&&a[st[top]]<a[i]) top--;
        rmx[i]=top?st[top]-1:n;st[++top]=i;//维护.
    }
    /*
        扫描线计数.
        把所有的最小值一个一个处理,假设a[i]可以作为最小值,那么他的范围是lmi[i]~rmi[i].
        我们假设从1开始扫描,看i成为最小值的区间,再拿最大值可以存在的区间去扫描它,然后到了这个点把不能成为最小值的i清理一下.
    */
    for(int i=1;i<=n;i++)
    {
        if(lmi[i]<=a[i]&&rmi[i]>=a[i]) L[lmi[i]].push_back(a[i]),R[rmi[i]].push_back(a[i]);
        if(lmx[i]<=a[i]&&rmx[i]>=a[i]) W[a[i]].push_back({lmx[i],rmx[i]});
    }
    for(int i=1;i<=n;i++)
    {
        for(auto x:L[i])   insert(x,1);
        for(auto x:W[i])   ans+=ask(x.r)-ask(x.l-1);
        for(auto x:R[i])   insert(x,-1);
    }
    printf("%lld\n",ans);
    return 0;
}