P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

题目背景

译自 COCI 2024/2025 #5 T3。$\texttt{2s,0.5G}$。满分为 $90$。

题目描述

给定正整数序列 $h_1,\ldots,h_n$。

对于区间 $[l,r]$，我们称 $i$（$l\le i\le r$）关于 $[l,r]$ 是好的，当且仅当：$h_i=\gcd(h_l,h_{l+1},\ldots,h_r)$。

对于 $i$，定义 $f(i)$ 表示：所有 $i$ 关于 $[l,r]$ 是好的区间中，$r-l+1$ 的最大值。

对于 $i=1,2,\ldots,n$，求出 $f(i)$。

输入格式

第一行，正整数 $n$。

第二行，$n$ 个正整数 $h_1,h_2,\ldots,h_n$。

输出格式

输出 $n$ 个正整数 $f(1),f(2),\ldots,f(n)$。

输入输出样例 #1

输入 #1

6
3 6 6 6 1 3

输出 #1

4 3 3 3 6 1

输入输出样例 #2

输入 #2

5
10 2 10 15 5

输出 #2

1 3 1 1 3

说明/提示

数据范围

对于 $100\%$ 的数据，保证 $1\le n,h_i\le 10^6$。

子任务编号	$n\le$	特殊性质	得分
$1$	$100$		$7$
$2$	$5\times 10^3$		$11$
$3$	$5\times 10^4$		$17$
$4$	$10^6$	A	$29$
$5$			$26$

特殊性质 A：$h_i\le 100$。

#5725. 「COCI 2024/2025 #5」Tornjevi

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #5 T3「Tornjevi」

在某条街道上，共有 $n$ 座塔，按 $1$ 到 $n$ 的顺序连续编号。每座塔都有其高度 $h_{i}$，单位为米。

对于一个由编号为 $l, l+1, \ldots, r$ 的塔组成的连续子序列，若满足 $h_{i}=\operatorname{gcd}(h_{l}, h_{l+1}, \ldots, h_{r})$，则称其中编号为 $i$ $(l \leq i \leq r)$ 的塔在该子序列中是好的。其中 $\operatorname{gcd}(a_{1}, a_{2}, \ldots, a_{k})$ 表示正整数集合 $a_{1}, a_{2}, \ldots, a_{k}$ 的最大公约数。

你的任务是针对每个 $i=1, 2, \ldots, n$，确定使编号为 $i$ 的塔成为好的塔的最长连续子序列的大小。连续子序列的大小定义为该序列中包含的塔的数量。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{6})$，代表塔的数量。

第二行按顺序包含 $n$ 个整数 $h_{1}, h_{2}, \ldots, h_{n}$ $(1 \leq h_{i} \leq 10^{6})$。

输出格式

在一行中按顺序输出上述问题中针对每个 $i=1, 2, \ldots, n$ 的答案。

样例 1

输入

6
3 6 6 6 1 3

输出

4 3 3 3 6 1

在前四座塔中，编号为 $1$ 的塔是好的。编号为 $2$，$3$ 和 $4$ 的塔在它们各自组成的子序列中是好的。塔 $5$ 在任何包含它的任意子序列中都是好的，因此答案将是 $6$（整个序列）。

样例 2

输入

5
10 2 10 15 5

输出

1 3 1 1 3

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$n \leq 100$
$2$	$11$	$n \leq 5000$
$3$	$17$	$n \leq 50000$
$4$	$29$	$h_{i} \leq 100$
$5$	$26$	无附加限制