解题思路
容易想到从小到大加数，维护每个点的子树大小。
可转化为维护每个点为 \(\max\) 时的 \([L,R]\) 区间。
然后需要写一个支持 【区间+1】、【区间取min】、单点加入、全局查询。
上个吉司机线段树即可。
注意点
-
吉司机线段树下推 \(fi\) 的标记的时候要注意 \(fi\) 的变化。
-
错误写法：
if(fi[rt<<1]>=fi[rt<<1|1])pushcov(rt<<1,tag[rt]); if(fi[rt<<1|1]>=fi[rt<<1])pushcov(rt<<1|1,tag[rt]); -
正确写法：
int x=fi[rt<<1]-fi[rt<<1|1]; if(x>=0)pushcov(rt<<1,tag[rt]); if(x<=0)pushcov(rt<<1|1,tag[rt]);
-
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1.5e5+10,M=N<<2,INF=1e9;
int n,a[N],pos[N];
namespace R{
int fi[M],se[M],cnt[M],siz[M];
int laz[M],tag[M];
ll sum[M];
void pushup(int rt){
siz[rt]=siz[rt<<1]+siz[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
fi[rt]=max(fi[rt<<1],fi[rt<<1|1]);
se[rt]=max(se[rt<<1],se[rt<<1|1]);
cnt[rt]=0;
if(fi[rt<<1]==fi[rt])cnt[rt]+=cnt[rt<<1];
else se[rt]=max(se[rt],fi[rt<<1]);
if(fi[rt<<1|1]==fi[rt])cnt[rt]+=cnt[rt<<1|1];
else se[rt]=max(se[rt],fi[rt<<1|1]);
}
void pushadd(int rt,int x){
if(!siz[rt])return;
laz[rt]+=x,sum[rt]+=1ll*x*siz[rt],fi[rt]+=x,se[rt]+=x;
}
void pushcov(int rt,int x){
if(!siz[rt])return;
sum[rt]+=1ll*x*cnt[rt],fi[rt]+=x,tag[rt]+=x;
}
void pushdown(int rt){
if(laz[rt]){
pushadd(rt<<1,laz[rt]);
pushadd(rt<<1|1,laz[rt]);
laz[rt]=0;
}
if(tag[rt]){
int x=fi[rt<<1]-fi[rt<<1|1];
if(x>=0)pushcov(rt<<1,tag[rt]);
if(x<=0)pushcov(rt<<1|1,tag[rt]);
tag[rt]=0;
}
}
void build(int l=1,int r=n,int rt=1){
laz[rt]=tag[rt]=0;
if(l==r){
sum[rt]=0;
fi[rt]=se[rt]=-INF;
cnt[rt]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int R,int x,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return pushadd(rt,x);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)update(L,R,x,l,mid,rt<<1);
if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void modify(int L,int R,int x,int l=1,int r=n,int rt=1){
if(x>=fi[rt])return;
if(L<=l&&r<=R&&x>=se[rt])return pushcov(rt,x-fi[rt]);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)modify(L,R,x,l,mid,rt<<1);
if(mid<R)modify(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void insert(int x,int y,int l=1,int r=n,int rt=1){
if(l==r){
siz[rt]=cnt[rt]=1;
fi[rt]=sum[rt]=y;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)insert(x,y,l,mid,rt<<1);
else insert(x,y,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(){
return sum[1];
}
int find(int x,int l=1,int r=n,int rt=1){
if(l==r)return fi[rt];
int mid=(l+r)>>1;
pushdown(rt);
return x<=mid?find(x,l,mid,rt<<1):find(x,mid+1,r,rt<<1|1);
}
}
namespace L{
int fi[M],se[M],cnt[M],siz[M];
int laz[M],tag[M];
ll sum[M];
void pushup(int rt){
siz[rt]=siz[rt<<1]+siz[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
fi[rt]=min(fi[rt<<1],fi[rt<<1|1]);
se[rt]=min(se[rt<<1],se[rt<<1|1]);
cnt[rt]=0;
if(fi[rt<<1]==fi[rt])cnt[rt]+=cnt[rt<<1];
else se[rt]=min(se[rt],fi[rt<<1]);
if(fi[rt<<1|1]==fi[rt])cnt[rt]+=cnt[rt<<1|1];
else se[rt]=min(se[rt],fi[rt<<1|1]);
}
void pushadd(int rt,int x){
if(!siz[rt])return;
laz[rt]+=x,sum[rt]+=1ll*x*siz[rt],fi[rt]+=x,se[rt]+=x;
}
void pushcov(int rt,int x){
if(!siz[rt])return;
sum[rt]+=1ll*x*cnt[rt],fi[rt]+=x,tag[rt]+=x;
}
void pushdown(int rt){
if(laz[rt]){
pushadd(rt<<1,laz[rt]);
pushadd(rt<<1|1,laz[rt]);
laz[rt]=0;
}
if(tag[rt]){
int x=fi[rt<<1]-fi[rt<<1|1];
if(x<=0)pushcov(rt<<1,tag[rt]);
if(x>=0)pushcov(rt<<1|1,tag[rt]);
tag[rt]=0;
}
}
void build(int l=1,int r=n,int rt=1){
laz[rt]=tag[rt]=0;
if(l==r){
sum[rt]=0;
fi[rt]=se[rt]=INF;
cnt[rt]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int R,int x,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return pushadd(rt,x);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)update(L,R,x,l,mid,rt<<1);
if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void modify(int L,int R,int x,int l=1,int r=n,int rt=1){
if(x<=fi[rt])return;
if(L<=l&&r<=R&&x<=se[rt])return pushcov(rt,x-fi[rt]);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)modify(L,R,x,l,mid,rt<<1);
if(mid<R)modify(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void insert(int x,int y,int l=1,int r=n,int rt=1){
if(l==r){
siz[rt]=cnt[rt]=1;
fi[rt]=sum[rt]=y;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)insert(x,y,l,mid,rt<<1);
else insert(x,y,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(){
return sum[1];
}
int find(int x,int l=1,int r=n,int rt=1){
if(l==r)return fi[rt];
int mid=(l+r)>>1;
pushdown(rt);
return x<=mid?find(x,l,mid,rt<<1):find(x,mid+1,r,rt<<1|1);
}
}
int c[N];
void add(int x,int y){
for(;x<=n;x+=x&-x)c[x]+=y;
}
void get(int x,int &y){
for(;x;x^=x&-x)y+=c[x];
}
int main(){
freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
L::build(),R::build();
for(int i=1,x,t;i<=n;i++){
add(x=pos[i],1),get(x,t=0);
L::insert(x,1),R::insert(x,i);
if(x<n){
R::update(x+1,n,1);
L::update(x+1,n,1);
L::modify(x+1,n,t+1);
}
if(x>1){
R::modify(1,x-1,t-1);
}
// for(int i=1;i<=n;i++){
// auto trs=[&](int x){
// return abs(x)<=n?x:-1;
// };
// fprintf(stderr,"(%d,%d)%c",trs(L::find(i)),trs(R::find(i)),"\n "[i<n]);
// }
printf("%lld\n",R::query()-L::query()+i);
}
return 0;
}