一、题目
二、解法
保留 \(\leq k\) 的数之后，考虑第 \(i\) 个数是作为极长段 \((l_i,r_i)\) 的最大值，那么答案是：
\[\sum_{i=1}^{k}r_i-l_i-1 \]我们先考虑计算 \(A=\sum_{i=1}^kr_i\)，考虑在增大 \(k\) 时动态插入一个数，设其位置是 \(p\)：
- 对于位置在它后面的位置 \(j\)，\(r_j\) 会增加 \(1\)
- \(r_p=k+1\)
- 对于在它前面的位置 \(j\)，\(r_j\) 需要和 \(p\) 取 \(\min\)
所以我们的数据结构要支持区间加法、全局查询、单点修改、区间取 \(\min\)；显然可以用势能线段树，主要是涉及区间加法有点难，可以先下传加法再下传 \(max\)，这样加法是对 \(max\) 没有影响的。
可以把原序列翻转，按上面的操作再做一次，那么得到的是 \(B=\sum_{i=1}^k k-l_i+1\)（因为全都翻转了），不难发现 \(\sum_{i=1}^kr_i-l_i-1=A+B-k(2+k)\)，那么我们得到了答案，时间复杂度 \(O(n\log^2n)\)
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 600005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,p[M],res[M],mx[M],cx[M];
int nx[M],num[M],sum[M],fl[M];
void fuck(int i,int c)
{
fl[i]+=c;sum[i]+=num[i]*c;
mx[i]+=c;cx[i]+=c;
}
void lim(int i,int c)
{
if(mx[i]<=c) return ;
sum[i]-=(mx[i]-c)*nx[i];
mx[i]=c;
}
void down(int i)
{
if(fl[i])
{
fuck(i<<1,fl[i]);
fuck(i<<1|1,fl[i]);
fl[i]=0;
}
lim(i<<1,mx[i]);
lim(i<<1|1,mx[i]);
}
void up(int i)
{
nx[i]=0;
num[i]=num[i<<1]+num[i<<1|1];
sum[i]=sum[i<<1]+sum[i<<1|1];
mx[i]=max(mx[i<<1],mx[i<<1|1]);
cx[i]=max(cx[i<<1],cx[i<<1|1]);
if(mx[i]==mx[i<<1]) nx[i]+=nx[i<<1];
if(mx[i]==mx[i<<1|1]) nx[i]+=nx[i<<1|1];
if(mx[i<<1]<mx[i]) cx[i]=max(cx[i],mx[i<<1]);
if(mx[i<<1|1]<mx[i]) cx[i]=max(cx[i],mx[i<<1|1]);
}
int add(int i,int l,int r,int L,int R)
{
if(L>r || l>R) return 0;
if(L<=l && r<=R)
{
fuck(i,1);
return num[i];
}
int mid=(l+r)>>1,res=0;down(i);
res+=add(i<<1,l,mid,L,R);
res+=add(i<<1|1,mid+1,r,L,R);
up(i);return res;
}
void ins(int i,int l,int r,int id,int c)
{
if(l==r)
{
nx[i]=num[i]=1;
mx[i]=sum[i]=c;
return ;
}
int mid=(l+r)>>1;down(i);
if(mid>=id) ins(i<<1,l,mid,id,c);
else ins(i<<1|1,mid+1,r,id,c);
up(i);
}
void zxy(int i,int l,int r,int L,int R,int c)
{
if(L>r || l>R) return ;
if(L<=l && r<=R)
{
if(mx[i]<=c) return ;
if(cx[i]<c)
{
lim(i,c);
return ;
}
}
int mid=(l+r)>>1;down(i);
zxy(i<<1,l,mid,L,R,c);
zxy(i<<1|1,mid+1,r,L,R,c);
up(i);
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
p[read()]=i;
for(int t=1;t<=2;t++)
{
for(int i=1;i<=4*n;i++)
mx[i]=cx[i]=num[i]=sum[i]=fl[i]=0;
for(int i=1;i<=n;i++)
{
int x=add(1,1,n,p[i]+1,n);
ins(1,1,n,p[i],i+1);
zxy(1,1,n,1,p[i]-1,i-x);
res[i]+=sum[1];
}
for(int i=1;i<=n;i++)
p[i]=n-p[i]+1;
}
for(int i=1;i<=n;i++)
printf("%lld\n",res[i]-i*(i+2));
}