GMOJ 6808
首先我们可以考虑当所有 \(a_i\) 不相等的情况，那一段区间 \(l,r\) 排好序后差值一定 \(\ge 1\)，因此如果要满足条件，相邻两项一定只能差一，也就是一个公差为一的等差数列。其项数为数列的 \(mx-mn+1\)，长度又为 \(r-l+1\)，故有：\(mx-mn=r-l\)。满足这个等式才能满足条件。
再进一步想，有重复的 \(a_i\) 该怎么办，也就是一段区间差值可以为 \(0\) 了，那我们设区间内相同数值的个数为 \(cnt\)，即 \(cnt= \sum {num_{a_i}-1}\)，\(num\) 就是 \(a_i\) 出现次数。于是便有了 \(mx-mn+cnt=r-l\) 时满足条件。
我们就选择枚举一个 \(r\)，这样 \(r\) 就成了已知量，于是移项可得：\(mx-mn+cnt+l=r\)。又因为不满足条件时， \(mx-mn+cnt+l \ge r\)，因此只需要用线段树维护左边那一坨的最小值，判断它是否等于 \(r\)，就能知道该区间是否合法。
怎么维护？首先思考新枚举到一个值 \(x\) 时 \(mx,mn\) 的变化。以 \(mx\) 为例：那么在 \(x\) 之前比 \(x\) 小的值所在的区间都会被改变，这些比 \(x\) 小的值可以使用单调栈来维护。如下图：
圆圈即为比 \(x\) 小的点的位置，每次在单调栈弹出栈头（\(smx[top]\)）时，就需要更新他们。具体的，在找到一个值后，以它前一个比\(x\)小的值的后一位为左端点（即 \(l1\)），当前为右端点（\(r1\)），这段区间的 \(mx\) 要变为 \(x\)，因此维护的一坨东西需要加上 \(x-smx[top]\)，并将 \(r\) 移到前一个比 \(x\) 小的数的位置（\(r2\)）（不然先前更新过的区间会被重复加）。这样 \(mx\) 就更新完了，\(mn\) 同理。
然后就是 \(cnt\)。我们只需记录一下上一个 \(x\) 出现的位置 \(lst_x\)，因为多加了一个 \(x\) 进来，因此 \([1,lst_x]\) 这段区间的 \(cnt+1\)，原式子也 \(+1\)。
式子中的 \(l\) 可以在刚枚举到 \(r\) 这个点时将这个点 \(+r\)，因为 \(mn,mx,cnt\) 此时都为 \(0\)。
还要注意我们要求合法区间个数，因此还要维护这个数，在 \(\text {pushup}\) 时根据左右儿子区间那坨柿子的大小更新即可。
统计答案就判一下柿子最小值是否等于 \(r\) 就行辣。
代码中的 \(mn\) 是 \(mx-mn+cnt+l\) 的最小值， \(cnt\) 是合法 \(l\) 个数。
code
#include<bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
int n;
int a[100005],b[100005],cnt;
ll ans;
int pos[100005];
int smn[100005],smx[100005],tmn,tmx;
map<int,int>wz;
struct Tree{
int l,r;
ll cnt;
ll mn;
ll ad;
}tr[400005];
void pushup(int p){
if(tr[ls].mn==tr[rs].mn)tr[p].cnt=tr[ls].cnt+tr[rs].cnt;
else if(tr[ls].mn<tr[rs].mn)tr[p].cnt=tr[ls].cnt;//哪边柿子值小就继承哪边
else tr[p].cnt=tr[rs].cnt;
tr[p].mn=min(tr[ls].mn,tr[rs].mn);
}
void pushdown(int p){
if(!tr[p].ad)return;
tr[ls].ad+=tr[p].ad;
tr[rs].ad+=tr[p].ad;
tr[ls].mn+=tr[p].ad;
tr[rs].mn+=tr[p].ad;
tr[p].ad=0;
}
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;
if(l==r){
tr[p].mn=0;
tr[p].cnt=1;
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,ll d){
if(l<=0||r<=0||l>r)return;
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].mn+=d;
tr[p].ad+=d;
return;
}
pushdown(p);
int mid=tr[p].l+tr[p].r>>1;
if(l<=mid)update(ls,l,r,d);
if(r>mid)update(rs,l,r,d);
pushup(p);
}
Tree query(int p,int l,int r){
if(tr[p].l>=l&&tr[p].r<=r)return tr[p];
pushdown(p);
int mid=tr[p].l+tr[p].r>>1;
if(r<=mid)return query(ls,l,r);
if(l>mid)return query(rs,l,r);
Tree ld=query(ls,l,r),rd=query(rs,l,r);
Tree res;
res.l=ld.l;res.r=rd.r;
if(ld.mn==rd.mn)res.cnt=ld.cnt+rd.cnt;
else if(ld.mn<rd.mn)res.cnt=ld.cnt;
else res.cnt=rd.cnt;
res.mn=min(ld.mn,rd.mn);
return res;
}
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
cin>>n;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
pos[i]=wz[a[i]];
wz[a[i]]=i;
}
build(1,1,n);
for(int i=1;i<=n;++i){
update(1,i,i,i);
int r=i-1;
while(tmx&&a[smx[tmx]]<a[i]){
update(1,smx[tmx-1]+1,r,a[i]-a[smx[tmx]]);
tmx--;
r=smx[tmx];
}
smx[++tmx]=i;
r=i-1;
while(tmn&&a[smn[tmn]]>a[i]){
update(1,smn[tmn-1]+1,r,a[smn[tmn]]-a[i]);
tmn--;
r=smn[tmn];
}
smn[++tmn]=i;
update(1,1,pos[i],1);
Tree res=query(1,1,i);
if(res.mn==i)ans+=res.cnt;
}
cout<<ans;
return 0;
}