配点: 100 点
問題文
AtCoder 王国最高的塔“AtCoder Tower”,有很多人在排队等候迎接圣诞节。 显示 N 装饰品。
装饰品 N 有多种颜色,每种颜色 它的编号为 1,色 2,色 3,..., 色 N 。首先,从“AtCoder Tower”左侧开始 第 i 个装饰品是彩色的 A_i 。 对于
现在,国王高桥希望通过选择和移除一些装饰品来使装饰品看起来“像样”。 “看起来不错”是指满足以下条件:全部指满足。
- 剩余装饰品的颜色数量为2 色或更少。
- 相邻装饰品没有相同颜色的地方。
例如,如果删除 [A] 和 [B] 等内容,它看起来会“不错”。
另一方面,如果像[C]或[D]那样删除它,它看起来就不会“好”。
顺便说一句,“AtCoder Tower”有圣诞节装饰品。 它将持续 Q+1 天。i 当天晚上,从左起 第 X_i 个装饰品的颜色是 它将更改为 Y_i 。
因此,i = 1, 2, ... Q+1 为每个问题找到以下答案。
- 如果高桥君,i 如果你想让装饰品在当天中午看起来“好看”,你至少需要去除多少个装饰品?
制約
- 1 \leq N \leq 3 \ 000
- 0 \leq Q \leq 7 \ 000
- 1 \leq X_i \leq N
- 1 \leq Y_i \leq N
- 1 \leq A_i \leq N
- 所有输入均为整数
部分点
该问题分为若干子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (2 点) N = 1,Q = 0.
- (11 点) N \leq 15,Q = 0.
- (12 点) A_i \leq 2,Y_i \leq 2.
- (13 点) N \leq 250,Q = 0.
- (18 点) Q = 0.
- (44 分) 没有额外的限制。
但是,对于子作业 6,分数如下。 如果所有满足
- Q \leq 600 的测试用例都得到正确回答, 给出24 点。 如果所有满足
- Q \leq 1 \ 500 的测试用例都被正确回答,那么5 点。 如果所有满足
- Q \leq 2 \ 500 的测试用例都被正确回答,那么5 点。 如果所有满足
- Q \leq 4 \ 500 的测试用例都被正确回答,那么5 点。 如果所有满足
- 如果所有测试用例都正确回答,5 点。 如果所有满足
子作业 3 的提示
在此子任务中,任意一天的装饰品的颜色 只有 1 和颜色 选择 2 。换句话说,当剩余的装饰品以“好看”的状态从左侧观看时,颜色 与 1, 2, 1, ... 或颜色交替 只有两个选项: 2, 1, 2, ... 。如果您正在做子作业 3,您可能需要考虑此提示。
入力
输入是按以下格式从标准输入给出的。 请输出超过
N A_1 A_2 A_3 ... A_N Q X_1 Y_1 X_2 Y_2 X_3 Y_3 : X_Q Y_Q
出力
Q+1 行。
在
i 行中,i 请打印出当天中午需要移除的最少装饰品数量,以使装饰品看起来“好看”。
入力例 1
1 1 0
出力例 1
0
在此输入示例中,即使装饰物未被移除,装饰物也是“状况良好”。
因此,
正确答案是输出0 。
入力例 2
10 1 3 4 2 3 1 4 2 1 4 0
出力例 2
4
如下图所示,4 如果你移除一件装饰品,它看起来会“不错”。
该输入示例满足子任务 2 的约束。
入力例 3
12 8 9 9 4 4 11 11 8 4 9 9 4 10 3 9 1 4 2 9 10 11 7 4 1 8 3 8 6 9 6 8 2 9
出力例 3
8 8 7 7 7 7 7 7 6 6 6
Q=10 因此, 输出必须跨越11 行。