#P14766. [ICPC 2024 Seoul R] Cards Flipping

    ID: 14682 远端评测题 1000ms 2048MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>图论树形数据结构并查集2024ICPC首尔

[ICPC 2024 Seoul R] Cards Flipping

Description

魔术师 B 在桌面上排成一排放置了 nn 张卡片。每张卡片的两面都有颜色。卡片的正面是朝上的一面。卡片的背面是朝下的一面。卡片的每一面都有一种颜色。我们希望找到正面朝上的颜色中,不同颜色的最大数量。在下面的例子中,桌面上依次排开了 5 张卡片。从左到右,卡片正面的颜色分别是紫色、红色、紫色、紫色、红色,如下图所示。从左到右,卡片背面的颜色分别是红色、紫色、蓝色、黄色、红色。

:::align{center} :::

如果我们翻转一张卡片,那么这张卡片的正面和背面就会交换。如果我们翻转从左数的第 33 张和第 44 张卡片,那么卡片正面的颜色会变成下面这样。

:::align{center} :::

此时正面朝上的不同颜色的数量变成了 44,这是这个例子中能得到的最大值。

给定在桌面上排成一排的 nn 张卡片以及卡片两面的颜色,请编写一个程序,输出正面朝上的颜色中不同颜色的最大数量。

Input Format

你的程序需要从标准输入读取数据。输入的第一行包含一个整数 nn1n200,0001 \leq n \leq 200,000),其中 nn 是卡片的数量。卡片从 11nn 编号。接下来的两行中,第一行包含从卡片 11 到卡片 nn 的正面颜色。第二行包含从卡片 11 到卡片 nn 的背面颜色。每种颜色由一个不超过 10610^{6} 的非负整数表示。

Output Format

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含正面朝上的颜色中不同颜色的最大数量。

5
0 1 0 0 1
1 0 2 3 1
4
2
3 5
5 1
2
3
0 1 0
1 0 2
3