题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
给定一个长度为 N 的序列 A1,A2,…,AN,该序列是 1 到 N 之间的所有整数的一个排列,也就是说,1 到 N 的每个整数恰好出现一次。
A 的一个子序列是通过从 A 中删除 0 个或多个元素得到的序列。
给定三个整数 x,y,z(1≤x,y,z≤N 且 y≤z),定义 f(x,y,z) 为满足以下条件的 A 的子序列所能取得的最大长度:
- 子序列中的元素只能从原序列中下标处于区间 [y,z] 的部分选取。也就是说,子序列只能由 Ay,Ay+1,…,Az 组成。
- 子序列中所有的元素值都不超过 x。
- 子序列必须是一个之字形序列(Zigzag)。
长度为 K 的序列 S1,S2,…,SK 是之字形序列,当且仅当对于所有满足 1≤i≤K−2 的 i,满足以下条件之一:
- 如果 Si<Si+1,则有 Si+1>Si+2;
- 如果 Si>Si+1,则有 Si+1<Si+2。
更具体地说,所有长度不超过 2 的序列都被认为是之字形序列。
请注意,空序列的长度为 0,它满足上述所有条件,因此总有 f(x,y,z)≥0。
现在,对于所有满足 1≤y≤z≤N 的整数对 (y,z),将所有 f(x,y,z) 的值相加,定义为 g(x)。
你的任务是:对于每个 x=1,2,…,N,计算并输出 g(x) 的值。
输入格式
第一行输入一个整数 N。
第二行输入 A1,A2,…,AN,各数之间以空格分隔。
输出格式
输出 N 行,第 i 行输出 g(i) 的值(1≤i≤N)。
3
1 2 3
3
7
9
6
3 1 4 6 5 2
10
16
22
34
40
46
提示
限制条件
- 所有输入均为整数。
- 2≤N≤200000
- 对于所有 i(1≤i≤N),有 1≤Ai≤N;
- 对于所有 i,j(1≤i<j≤N),有 Ai=Aj(即 A 是一个排列)。
子任务
- (10 分)N≤15
- (13 分)N≤100
- (17 分)N≤500
- (22 分)N≤5000
- (38 分)无附加限制
翻译由 ChatGPT-4o 完成