← 返回题目列表

AtCoder · pakencamp_2019_day3_f

F. 圣诞装饰2

中文机器翻译题面 查看原题

配点: 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
  • 所有输入均为整数

部分点

该问题分为若干子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (2 点) N = 1,Q = 0.
  2. (11 点) N \leq 15,Q = 0.
  3. (12 点) A_i \leq 2,Y_i \leq 2.
  4. (13 点) N \leq 250,Q = 0.
  5. (18 点) Q = 0.
  6. (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 行。