跳蚤国计算机协会 UOI 主席 “王中王” 认为 UOI 决赛不具有观赏性。

\n

比如蟋蟀国的比赛，选手都需要在初赛快速 AK 才能晋级决赛，但 UOI 决赛只需要通过不到一半的题目就可以获得三十二强。

\n

但是经过 UOI 系列委员会的商讨，比赛难度并没有被下调，因此王中王决定黑幕一些比赛结果。

\n

具体来说，UOI 决赛总 $n$ 天，有 $m$ 名选手参加。现在王中王通过第六感得知，如果不加干预第 $i$ 天的比赛，那么第 $a_i$ 位选手将会胜出，但王中王每天可以将当天题目提前透露给任意一名选手。如果王中王透露了第 $i$ 天的题目，获得题目的选手将会成为那天比赛的胜利者，但他认为这样做比赛的合理性会降低 $w_i$。

\n

不妨假设黑幕后每天的胜者依次为 $b_1, b_2, \\dots, b_n$。王中王相信观众更喜欢看到“绝对强者”之间的对决，因此他认为一段赛程 $[l, r]$ 是“好看”的，当且仅当在该段赛程中，成为过胜者的选手数不超过二，即 $|\\{b_l, b_{l+1}, \\dots, b_r\\}| \\leq 2$。

\n

而每一段“好看”的赛程，王中王认为都会让比赛的合理性增加 $1$。

\n

而由于 UOI 决赛随时面临着缺投倒闭的风险，因此王中王想知道对于所有 $k = 1, 2, \\dots, n$，如果 UOI 决赛只举办前 $k$ 天的比赛，比赛的合理性最高能是多少？

\n

输入格式

\n

第一行两个正整数 $n,m$。

\n

第二行 $n$ 个正整数 $a_1, a_2, \\dots, a_n$。

\n

第三行 $n$ 个非负整数 $w_1, w_2, \\dots, w_n$。

\n

输出格式

\n

一行 $n$ 个数，表示每个前缀的答案。

\n\n\n

统计

递交统计

【UR #32】王之钦定

信息

状态

开发

支持

关于

还没有账户？

登录