Codeforces

分析

考虑一个好区间实际上是 $\max-\min=r-l$。

把所有询问按右端点排序，然后扫描线，则我们需要维护每个左端点到右端点的信息。

考虑每个左端点维护 $(\max-\min)-(r-l)$，显然这个东西是 $\geq 0$ 的，所以我们只需要维护最小值出现次数即可，可以用线段树维护。在右移右端点时需要更新信息，用单调栈维护最值即可。

但是我们要求的是所有区间，而不是右端点是 $r$ 的所有区间。

我们打一个标记 $addc$，表示当前最小值出现次数的贡献要算到答案里多少次。那么每次右移右端点时，我们先把 $[1,n]$ 的 $addc$ 加上 $1$，就能维护左端点是某个位置、右端点 $\leq r$ 的好区间个数了。询问就直接区间查询即可。

需要注意的是，在下放 $addc$ 时，只能下放到最小值等于它的儿子中（因为可能一次移动右端点还未完成，所以不是 $=0$）。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=120000+10;

int n,Q,p[N]; ll ans[N];
vector<pair<int,int>> q[N];
int sta1[N],top1,sta2[N],top2;

#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2],minc[N<<2],addv[N<<2],addc[N<<2];
ll ansv[N<<2];

void update_min(int o,int w) { minv[o]+=w,addv[o]+=w; }
void update_cnt(int o,int w) { ansv[o]+=1ll*w*minc[o],addc[o]+=w; }
void pushup(int o) {
    minv[o]=min(minv[ls],minv[rs]);
    ansv[o]=ansv[ls]+ansv[rs];
    minc[o]=0;
    if (minv[o]==minv[ls]) minc[o]+=minc[ls];
    if (minv[o]==minv[rs]) minc[o]+=minc[rs];
}
void pushdown(int o) {
    if (addv[o]) update_min(ls,addv[o]),update_min(rs,addv[o]),addv[o]=0;
    if (addc[o]) {
        if (minv[o]==minv[ls]) update_cnt(ls,addc[o]);
        if (minv[o]==minv[rs]) update_cnt(rs,addc[o]);
        addc[o]=0;
    }
}

void build(int o,int l,int r) {
    minv[o]=l,minc[o]=1;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void modify_min(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update_min(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify_min(ls,l,mid,ql,qr,w);
    if (qr>mid) modify_min(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
ll query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return ansv[o];
    int mid=(l+r)>>1; ll res=0; pushdown(o);
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

int main() {
    n=read();
    for (int i=1;i<=n;++i) p[i]=read();
    Q=read();
    for (int i=1;i<=Q;++i) {
        int l=read(),r=read();
        q[r].emplace_back(l,i);
    }
    build(1,1,n);
    for (int i=1;i<=n;++i) {
        update_min(1,-1);
        while (top1&&p[i]>p[sta1[top1]]) {
            modify_min(1,1,n,sta1[top1-1]+1,sta1[top1],p[i]-p[sta1[top1]]);
            --top1;
        }
        sta1[++top1]=i;
        while (top2&&p[i]<p[sta2[top2]]) {
            modify_min(1,1,n,sta2[top2-1]+1,sta2[top2],p[sta2[top2]]-p[i]);
            --top2;
        }
        sta2[++top2]=i;
        update_cnt(1,1);
        for (auto j:q[i])
            ans[j.second]=query(1,1,n,j.first,i);
    }
    for (int i=1;i<=Q;++i) printf("%lld\n",ans[i]);
    return 0;
}