#P12665. [KOI 2023 Round 2] ZigZag

[KOI 2023 Round 2] ZigZag

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 NN 的序列 A1,A2,,ANA_1, A_2, \dots, A_N,该序列是 11NN 之间的所有整数的一个排列,也就是说,11NN 的每个整数恰好出现一次。

AA 的一个子序列是通过从 AA 中删除 00 个或多个元素得到的序列。

给定三个整数 x,y,zx, y, z1x,y,zN1 \leq x, y, z \leq Nyzy \leq z),定义 f(x,y,z)f(x, y, z) 为满足以下条件的 AA 的子序列所能取得的最大长度

  1. 子序列中的元素只能从原序列中下标处于区间 [y,z][y, z] 的部分选取。也就是说,子序列只能由 Ay,Ay+1,,AzA_y, A_{y+1}, \dots, A_z 组成。
  2. 子序列中所有的元素值都不超过 xx
  3. 子序列必须是一个之字形序列(Zigzag)

长度为 KK 的序列 S1,S2,,SKS_1, S_2, \dots, S_K之字形序列,当且仅当对于所有满足 1iK21 \leq i \leq K - 2ii,满足以下条件之一:

  • 如果 Si<Si+1S_i < S_{i+1},则有 Si+1>Si+2S_{i+1} > S_{i+2}
  • 如果 Si>Si+1S_i > S_{i+1},则有 Si+1<Si+2S_{i+1} < S_{i+2}

更具体地说,所有长度不超过 22 的序列都被认为是之字形序列。

请注意,空序列的长度为 00,它满足上述所有条件,因此总有 f(x,y,z)0f(x, y, z) \geq 0

现在,对于所有满足 1yzN1 \leq y \leq z \leq N 的整数对 (y,z)(y, z),将所有 f(x,y,z)f(x, y, z) 的值相加,定义为 g(x)g(x)

你的任务是:对于每个 x=1,2,,Nx = 1, 2, \dots, N,计算并输出 g(x)g(x) 的值。

输入格式

第一行输入一个整数 NN
第二行输入 A1,A2,,ANA_1, A_2, \dots, A_N,各数之间以空格分隔。

输出格式

输出 NN 行,第 ii 行输出 g(i)g(i) 的值(1iN1 \leq i \leq N)。

3
1 2 3
3
7
9
6
3 1 4 6 5 2
10
16
22
34
40
46

提示

限制条件

  • 所有输入均为整数。
  • 2N2000002 \leq N \leq 200\,000
  • 对于所有 ii1iN1 \leq i \leq N),有 1AiN1 \leq A_i \leq N
  • 对于所有 i,ji, j1i<jN1 \leq i < j \leq N),有 AiAjA_i \ne A_j(即 AA 是一个排列)。

子任务

  1. (10 分)N15N \leq 15
  2. (13 分)N100N \leq 100
  3. (17 分)N500N \leq 500
  4. (22 分)N5000N \leq 5\,000
  5. (38 分)无附加限制

翻译由 ChatGPT-4o 完成