题意
给定一个序列，定义连续区间为区间的数排序后，任意两个相邻的数之差不超过1。
分析
- 假设区间最大值为(max),最小值为(min)，不同数个数为(cnt)，那么问题转化为求满足(max-min-cnt==1)的区间个数。
- 统计满足条件的区间个数可以考虑用线段树，主要有三个步骤：
- 枚举右端点(R)
- 线段树维护当前所有左端点，即每个叶子节点((i,i))，表示序列区间([i,R])
- 统计答案，以(R)为右端点的所有区间，即线段树根节点((1,n))
- 更新区间分为两部分
- 第一部分是(cnt)，也相当于也就是要更新当前(R)，前面有多少个区间([i,R])以(a[R])作为一个新的不同的数字，显然就是(a[R])上一次出现的位置+1，因为公式中是(-cnt)，所以更新值为-1。
- 第二部分是(max)和(min)，利用单调栈来维护，当从栈中弹出时，可以得到该元素作为最大/最小值延伸的区间，更新值就是该元素和新的最大/最小值(a[R])之间的差值。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const int INF=0x3f3f3f3f;
int T,n,a[N];
//线段树(1-n)维护的是当前R作为右端点，([1,R],[2,R]...[R,R])这些区间的情况，也就是一个点代表一个区间
struct ST{
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
//维护区间(mx-mn-cnt)的最小值和最小值的个数
int sm[N*4],mn[N*4],lz[N*4];
void pushup(int i){
mn[i]=min(mn[ls],mn[rs]);
if(mn[ls]==mn[rs]){
sm[i]=sm[ls]+sm[rs];
}else if(mn[ls]<mn[rs]){
sm[i]=sm[ls];
}else{
sm[i]=sm[rs];
}
}
void pushdown(int i){
if(lz[i]){
lz[ls]+=lz[i];
lz[rs]+=lz[i];
mn[ls]+=lz[i];
mn[rs]+=lz[i];
lz[i]=0;
}
}
void build(int i,int l,int r){
lz[i]=0;
if(l==r){
mn[i]=INF;
sm[i]=0;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
//单点插入/修改，即开始增加以ｐ为左端点的区间贡献
void insert(int i,int l,int r,int p){
if(l==r){
//此时以ｐ为左端点的区间只有[p,p]，因此mx-mn-cnt=-1，为合法区间
mn[i]=-1;
sm[i]=1;
return;
}
pushdown(i);
if(p<=mid){
insert(ls,l,mid,p);
}else{
insert(rs,mid+1,r,p);
}
pushup(i);
}
//区间更新(mx-mn-cnt)
void update(int i,int l,int r,int ql,int qr,int v){
if(ql<=l && qr>=r){
lz[i]+=v;
mn[i]+=v;
return;
}
pushdown(i);
if(ql<=mid){
update(ls,l,mid,ql,qr,v);
}
if(qr>mid){
update(rs,mid+1,r,ql,qr,v);
}
pushup(i);
}
}ac;
map<int,int> lst;
int smx[N],smn[N];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
ll ans=0;
scanf("%d",&n);
ac.build(1,1,n);
lst.clear();
int mxt=0,mnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ac.insert(1,1,n,i);
//单调栈维护最大最小值区间
//维护一个小顶栈，那么弹出来的元素作为最大值延伸的位置是[smx[mxt-1]+1,smx[mxt]]
while(mxt>0 && a[smx[mxt]]<=a[i]){
ac.update(1,1,n,smx[mxt-1]+1,smx[mxt],a[i]-a[smx[mxt]]);
mxt--;
}
smx[++mxt]=i;
while(mnt>0 && a[smn[mnt]]>=a[i]){
ac.update(1,1,n,smn[mnt-1]+1,smn[mnt],-(a[i]-a[smn[mnt]]));
mnt--;
}
smn[++mnt]=i;
//map维护上一次出现位置
int L=0;
if(lst.find(a[i])!=lst.end()){
L=lst[a[i]]+1;
}else{
L=1;
}
if(L<=i-1){
//比如3 1 2 4 3，最新加入的3，所以[1 2 4 3],[2 4 3],[4 3]都应该更新不同数的个数
//由于维护的是mx-mn-cnt，所以是-1
ac.update(1,1,n,L,i-1,-1);
}
lst[a[i]]=i;
//以当前a[i]为右端点元素的合法区间个数
//因为加入新节点(R,R)后，mn[1]肯定为-1，所以无需判断
ans+=1ll*ac.sm[1];
}
printf("Case #%d: %lld
",cas,ans);
}
}