#P13995. qoj 16226 Depth of Interval

qoj 16226 Depth of Interval

区间深度(Depth of Interval)

给定正整数 NN 和一个长度为 NN 的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\dots,P_N),其中 PP 是 (1,2,…,N)(1,2,\dots,N) 的一个排列。

对整数对 (L,R)(L,R),递归定义函数 f(L,R)f(L,R):

  • 若 1≤L<R≤N1\le L<R\le N:在子数组 PL,PL+1,…,PRP_L,P_{L+1},\dots,P_R 中,设最小值出现在位置 aa(即元素为 PaP_a),次小值出现在位置 bb(即元素为 PbP_b)。则f(L,R)=f(min⁡(a,b)+1, max⁡(a,b)−1)+1.f(L,R)=f(\min(a,b)+1,\ \max(a,b)-1)+1.
  • 否则(即 L≥RL\ge R 或不满足范围),定义 f(L,R)=0f(L,R)=0。

现在对每个 k=1,2,…,Nk=1,2,\dots,N,请你求出满足 f(L,R)=kf(L,R)=k 的整数对 (L,R)(L,R) 的个数。


输入格式

输入格式如下:

N
P1 P2 ... PN

其中 2≤N≤3×1052\le N\le 3\times 10^5,并且 (P1,…,PN)(P_1,\dots,P_N) 是 (1,2,…,N)(1,2,\dots,N) 的一个排列。


输出格式

输出 NN 行。第 kk 行输出满足 f(L,R)=kf(L,R)=k 的整数对 (L,R)(L,R) 的个数。


样例

7
2 6 5 1 4 7 3
14
7
0
0
0
0
0
5
1 2 3 4 5
10
0
0
0
0
9
8 6 2 4 9 7 3 5 1
25
8
3
0
0
0
0
0
0

说明(对应样例 1)

样例 1 中,f(1,7)f(1,7) 的计算过程为:区间 [1,7][1,7] 的最小值在 a=4a=4,次小值在 b=1b=1,因此 f(1,7)=f(2,3)+1f(1,7)=f(2,3)+1。接着区间 [2,3][2,3] 的最小值在 a=3a=3,次小值在 b=2b=2,所以 f(2,3)=f(3,2)+1f(2,3)=f(3,2)+1,而 f(3,2)=0f(3,2)=0,故 f(1,7)=2f(1,7)=2。