P17631 【UR #32】王之钦定

原题链接：https://uoj.ac/problem/1005 部分数据重造，数据范围有所修改。

跳蚤国计算机协会 UOI 主席 “王中王” 认为 UOI 决赛不具有观赏性。 比如蟋蟀国的比赛，选手都需要在初赛快速 AK 才能晋级决赛，但 UOI 决赛只需要通过不到一半的题目就可以获得三十二强。 但是经过 UOI 系列委员会的商讨，比赛难度并没有被下调，因此王中王决定黑幕一些比赛结果。 具体来说，UOI 决赛总 $n$ 天，有 $m$ 名选手参加。现在王中王通过第六感得知，如果不加干预第 $i$ 天的比赛，那么第 $a_i$ 位选手将会胜出，但王中王每天可以将当天题目提前透露给任意一名选手。如果王中王透露了第 $i$ 天的题目，获得题目的选手将会成为那天比赛的胜利者，但他认为这样做比赛的合理性会降低 $w_i$。 不妨假设黑幕后每天的胜者依次为 $b_1, b_2, \dots, b_n$。王中王相信观众更喜欢看到“绝对强者”之间的对决，因此他认为一段赛程 $[l, r]$ 是“好看”的，当且仅当在该段赛程中，成为过胜者的选手数不超过二，即 $|\{b_l, b_{l+1}, \dots, b_r\}| \leq 2$。 而每一段“好看”的赛程，王中王认为都会让比赛的合理性增加 $1$。 而由于 UOI 决赛随时面临着缺投倒闭的风险，因此王中王想知道对于所有 $k = 1, 2, \dots, n$，如果 UOI 决赛只举办前 $k$ 天的比赛，比赛的合理性最高能是多少？

第一行两个正整数 $n,m$。 第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。 第三行 $n$ 个非负整数 $w_1, w_2, \dots, w_n$。

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

### 数据范围 $1 \leq n \leq 1010, 1 \leq a_i \leq m\leq 120, 0 \leq w_i \leq 10^6$ | 子任务编号 | $n\le$ | $m\le$ | 分值 | | :--------: | :----: | :----: | :--: | | $1$ | $1000$ | $2$ | $1$ | | $2$ | $8$ | $8$ | $6$ | | $3$ | $30$ | $30$ | $9$ | | $4$ | $60$ | $40$ | $12$ | | $5$ | $1000$ | $3$ | $15$ | | $6$ | $120$ | $80$ | $15$ | | $7$ | $300$ | $120$ | $12$ | | $8$ | $600$ | $120$ | $12$ | | $9$ | $1000$ | $120$ | $18$ |