A - Depth of Interval
解説
/
/
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正整数 N と (1,2,\dots ,N) の順列 P=(P_1,P_2,\dots ,P_N) が与えられます。
整数組 (L,R) に対して、f(L,R) を次のように再帰的に定めます。
- 1\le L\lt R\le N のとき、整数 a, b を P_L,P_{L+1},\dots, P_{R} のうち最も小さいものとその次に小さいものがそれぞれ P_a,P_b となるように定義する。f(L, R) = f(\min(a, b) + 1, \max(a, b) - 1) + 1 と定める。
- そうでないとき、f(L,R)=0 と定める。
k=1,2,\dots, N のそれぞれについて、整数組 (L,R) であって f(L,R)=k を満たすものの個数を求めてください。
制約
- 入力はすべて整数
- 2\le N\le 3\times 10^5
- (P_1,P_2,\dots, P_N) は (1,2,\dots, N) の順列
入力
入力は以下の形式で与えられる。
N P_1 P_2 \dots P_N
出力
N 行出力せよ。k=1,2,\dots, N について、k 行目には、整数組 (L,R) であって f(L,R)=k を満たすものの個数を出力せよ。
入力例 1
7 2 6 5 1 4 7 3
出力例 1
14 7 0 0 0 0 0
f(1,7) は次のように定められます。P_1,P_2,\dots, P_7 のうち最も小さいものとその次に小さいものはそれぞれ P_4,P_1 です。したがって f(1,7)=f(2,3)+1 です。
f(2,3) は次のように定められます。P_2,P_3 のうち最も小さいものとその次に小さいものはそれぞれ P_3,P_2 です。したがって f(2,3)=f(3,2)+1 です。
f(3,2)=0 なので f(2,3)=1 です。したがって f(1,7)=2 です。
入力例 2
5 1 2 3 4 5
出力例 2
10 0 0 0 0
入力例 3
9 8 6 2 4 9 7 3 5 1
出力例 3
25 8 3 0 0 0 0 0 0