配点: 100 点
問題
皮塔罗是 一套 N 卡片。 2 我有一套。1 第一套卡片包括 它被命名为 A ,并按从头开始的顺序 写入数字 a_1 如果要将其更改为输出最多为 a_N 。2 第一套卡片包括 它被命名为 B ,并按从头开始的顺序 写入数字 b_1 如果要将其更改为输出最多为 b_N 。
皮塔罗卡片套装 您可以随时重新排列 B ,次数不限。
Pitaro 玩以下游戏。 执行 N 次。
- i (1 \leq i \leq N) 第二场比赛。卡组 A 开始 i 按顺序写在纸张上的一系列数字。 C_i 。
- 卡组 B 通过按顺序排列每张卡片上写的数字来创建数字序列。 卡片设置为最大化 C_i 连续出现的次数 排序 B 。
- 但是,C_i 它们的出现位置不得重叠。例如,一个数列
{1 2 1 2 1 2 1 2}是{(1 2 1 2) (1 2 1 2)}如果我们考虑序列 它已出现{1 2 1 2}是 从 2 次。这时,{(1 2 1 2) 1 2 1 2},{1 2 (1 2 1 2) 1 2},{1 2 1 2 (1 2 1 2)}的 3 无法计数。 游戏的得分是 - 卡组 B 通过按顺序排列每张卡片上写的数字来创建数字序列。 卡片设置为最大化 C_i 连续出现的次数。
编写一个程序来查找 Pitaro 在每场比赛中可以获得的分数。
制約
- 所有输入均为整数。
- 2 \leq N \leq 100\,000.
- 1 \leq a_i, b_i \leq 100\,000 (1 \leq i \leq N).
小課題
- (16 点) N \leq 8.
- (10 点) a_i = 1 (1 \leq i \leq N).
- (24 点) N \leq 1\,000.
- (50 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N a_1 a_2 \cdots a_N b_1 b_2 \cdots b_N
出力
到标准输出N 行。i (1 \leq i \leq N) 行包含i 输出Pitaro在第二场比赛中可以获得的分数。 通过使用
入力例 1
5 1 2 3 4 5 1 2 2 1 3
出力例 1
2 2 1 0 0
例如
当计算像 {1 2 3 2 1} 排序
可能会出现 C_1 从 2 個,{3 1 2 1 2} 排序
可能会出现 C_2 从 2 個,{2 1 2 3 1} 排序
可能会出现 C_3 从 1 。
这个输入/输出示例是一个小任务。 1,3,4 很满意。 从
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
5 2 1 1 1
卡组 B 获得的可能序列是
只有 {1 1 1 1 1} 。
这个输入/输出示例是一个小任务。 1,2,3,4 很满意。 从