牛客练习赛66 E 骚区间线段树+扫描线

题目链接：https://ac.nowcoder.com/acm/contest/6112/E?&headNav=acm
题目大意：
图片说明
$图片说明$

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define LL long long
#define mid (l+r>>1)
using namespace std;

const int N=1e6+7;
LL INF=0;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct SegTree {
    LL T[N<<2], pos[N<<2];
    inline void pushup(int o) {
        if(T[o<<1]<T[o<<1|1]){
            T[o]=T[o<<1]; pos[o]=pos[o<<1];
        }
        else{
            T[o]=T[o<<1|1]; pos[o]=pos[o<<1|1];
        }
    }
    void BT(int o, int l, int r){
        if(l==r){
            T[o]=INF; pos[o]=l;
            return ;
        }
        BT(o<<1, l, mid); BT(o<<1|1, mid+1, r);
        pushup(o);
    }
    void add(int o,int l,int r,int pos,LL v){//修改 T[o]=v
        if(l==r) { T[o]=v; return; }
        pos<=mid ? add(o<<1,l,mid,pos,v) : add(o<<1|1,mid+1,r,pos,v);
        pushup(o);
    }
    pair<int, int> query(int o,int l,int r,int ql,int qr){//查询区间最大值

        if(l>qr||r<ql) return {INF, INF};
        if(l>=ql&&r<=qr) return {T[o], pos[o]};
        return min(query(o<<1,l,mid,ql,qr),query(o<<1|1,mid+1,r,ql,qr));
    }

}T;

LL s[1000005];
void add(LL x,LL z) {for (LL i=x;i<=N;i+=(i&(-i))) s[i]+=z;}
LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;}
LL ask(LL x, LL y){return ask(y)-ask(x-1);}

int a[1000050], l[1000050], r[1000050];
vector<pair<int, int> > v1[1000050], v2[1000050];

int main() {
    int n; scanf("%d", &n);
    INF=n+1;
    T.BT(1, 1, n);
    for(int i=1; i<=n; i++){
        a[i]=read();
        T.add(1, 1, n, a[i], i);
    }
    /*预处理l, r*/
    for(int i=1; i<=n; i++){
        pair<int , int> pos1=T.query(1, 1, n, 1, a[i]-1);
        l[i]=pos1.first;
        T.add(1, 1, n, pos1.second, INF);
        pair<int , int> pos2=T.query(1, 1, n, 1, a[i]-1);
        r[i]=pos2.first-1;
        T.add(1, 1, n, pos1.second, pos1.first);
        T.add(1, 1, n, a[i], INF);
    }
    INF=0;
    for(int i=1; i<=n; i++){
        T.add(1, 1, n, a[i], -i);
    }
    /*预处理L, R*/
    for(int i=n; i>=1; i--){
        pair<int , int> pos1=T.query(1, 1, n, a[i]+1, n);
        int R=-pos1.first;
        T.add(1, 1, n, pos1.second, INF);
        pair<int , int> pos2=T.query(1, 1, n, a[i]+1, n);
        int L=-pos2.first+1;
        T.add(1, 1, n, pos1.second, pos1.first);
        T.add(1, 1, n, a[i], INF);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 a = S.upper_bound(id);
        if (a == S.end()) continue;
        Inc[*a].push_back(id);
        a++;
        if (a != S.end()) Dec[(*a) - 1].push_back(id);
    }

    S.clear();
    for (int i = n; i >= 1; i--) {
        int id = rev[i];
        S.insert(-id);
        auto a = S.upper_bound(-id);
        if (a == S.end()) continue;
        qr[id] -= (*a);
        a++;
        if (a == S.end()) ql[id] = 1;
        else ql[id] -= (*a) - 1;
    }
        if(L<=R){
            v1[L].push_back({1, i});
            v2[R].push_back({-1, i});
        }
    }
    LL ANS=0;
    for(int i=1; i<=n; i++){
        for(auto x: v1[i]){//加入
            add(x.second, x.first);
        }
        if(l[i]<=r[i]){
            ANS+=ask(l[i], r[i]);
        }
        for(auto x: v2[i]){//删除 
            add(x.second, x.first);
        }
    }
    printf("%lld\n", ANS);

    return 0;
}
/* set预处理
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 a = S.upper_bound(id);
    if (a == S.end()) continue;
    Inc[*a].push_back(id);
    a++;
    if (a != S.end()) Dec[(*a) - 1].push_back(id);
}

S.clear();
for (int i = n; i >= 1; i--) {
    int id = rev[i];
    S.insert(-id);
    auto a = S.upper_bound(-id);
    if (a == S.end()) continue;
    qr[id] -= (*a);
    a++;
    if (a == S.end()) ql[id] = 1;
    else ql[id] -= (*a) - 1;
}
*/