对于这一类析合树问题有简单的线段树扫描线做法：考虑一个长为 \(len\) 的区间内一定有 \(len-1\) 个数值相邻的对，于是每次新加一个数 \(a_i\) 可以考虑相邻的两个数的出现位置 \(p\)，若 \(p\le i\) 就对 \([1,p]\) 区间加，表示左端点在 \([1,p]\) 的区间内多出一个相邻对
接下来的问题是一个线段树对历史最值求和的问题，可以设计两类标记，一个是 \(\text{maxcnt}\)，另一个是对最值加 \(1\) 的标记，考虑如何合并标记序列，发现只有当父结点的 \(\max\) 与儿子相同时整个标记序列才是有贡献的，所以可以直接下传，不需要考虑顺序问题
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 500005
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
struct MaxCnt{int max,cnt;};
MaxCnt operator+(MaxCnt x,MaxCnt y){
MaxCnt res;res.max=max(x.max,y.max);
res.cnt=x.cnt*(x.max==res.max)+y.cnt*(y.max==res.max);
return res;
}
int n,q,p[N],ip[N],ans[N];
vector<pair<int,int>>que[N];
namespace SGT{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
MaxCnt Max[N<<2];int Sum[N<<2],Tag[N<<2],Lzy[N<<2];
void Pushup(int k){Max[k]=Max[ls]+Max[rs];Sum[k]=Sum[ls]+Sum[rs];}
void Add(int k,int v){Sum[k]+=Max[k].cnt*v;Lzy[k]+=v;}
void Update(int k,int v){Max[k].max+=v;Tag[k]+=v;}
void Pushdown(int k,int l,int r){
if(Tag[k])Update(ls,Tag[k]),Update(rs,Tag[k]),Tag[k]=0;
if(Lzy[k]){
if(Max[k].max==Max[ls].max)Add(ls,Lzy[k]);
if(Max[k].max==Max[rs].max)Add(rs,Lzy[k]);
Lzy[k]=0;
}
}
void Build(int k,int l,int r){
if(l==r)return void(Max[k]=(MaxCnt){l,1});
Build(ls,l,mid);Build(rs,mid+1,r);Pushup(k);
}
void Modify(int k,int l,int r,int x,int y,int z){
if(l>=x&&r<=y)return Update(k,z);
Pushdown(k,l,r);
if(x<=mid)Modify(ls,l,mid,x,y,z);
if(mid<y)Modify(rs,mid+1,r,x,y,z);
Pushup(k);
}
void Change(int k,int l,int r,int x,int y,int z){
if(l>=x&&r<=y)return Max[k].max==z?Add(k,1):void();
Pushdown(k,l,r);
if(x<=mid)Change(ls,l,mid,x,y,z);
if(mid<y)Change(rs,mid+1,r,x,y,z);
Pushup(k);
}
int Query(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return Sum[k];
Pushdown(k,l,r);
if(y<=mid)return Query(ls,l,mid,x,y);
if(mid<x)return Query(rs,mid+1,r,x,y);
return Query(ls,l,mid,x,y)+Query(rs,mid+1,r,x,y);
}
}
using namespace SGT;
signed main(){
n=read();Build(1,1,n);
for(int i=1;i<=n;i++)ip[p[i]=read()]=i;
q=read();
for(int i=1,l,r;i<=q;i++)l=read(),r=read(),que[r].emplace_back(l,i);
for(int i=1;i<=n;i++){
if(p[i]>1&&ip[p[i]-1]<=i)Modify(1,1,n,1,ip[p[i]-1],1);
if(p[i]<n&&ip[p[i]+1]<=i)Modify(1,1,n,1,ip[p[i]+1],1);
Change(1,1,n,1,i,i);
for(auto u:que[i])ans[u.second]=Query(1,1,n,u.first,i);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}