← 返回题目列表

AtCoder · arc149_b

B. 两个 LIS 总和

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

分数: 500 点

问题陈述

对于序列 P = (P_1, \ldots, P_N),让 \mathrm{LIS}(P) 表示最长递增子序列的长度。

给你排列 A = (A_1, \ldots, A_N) 和 B = (B_1, \ldots, B_N) 的整数来自 1 通过 N。您可以对这些序列执行以下操作任意次数(可能为零)。

  • 选择一个整数 i 这样 1\leq i\leq N-1。互换 A_i 和 A_{i+1},并交换 B_i 和 B_{i+1}.

找到最大可能的最终值 \mathrm{LIS}(A) + \mathrm{LIS}(B).

什么是最长递增子序列?

序列的子序列是通过从原始序列中删除零个或多个元素,然后在不改变顺序的情况下连接剩余元素而获得的序列。 例如, (10,30) 是以下序列的子序列 (10,20,30),但是 (20,10) 不是以下的子序列 (10,20,30).

序列的最长递增子序列是该序列的严格递增子序列中长度最大的子序列。

约束

  • 2\leq N\leq 3\times 10^5
  • 1\leq A_i\leq N
  • 1\leq B_i\leq N
  • A_i\neq A_j 和 B_i\neq B_j,如果 i\neq j.

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_N
B_1 \ldots B_N

输出

打印最大可能的最终值 \mathrm{LIS}(A) + \mathrm{LIS}(B).


示例输入 1

5
5 2 1 4 3
3 1 2 5 4

示例输出 1

8

这是实现的一种方法 \mathrm{LIS}(A) + \mathrm{LIS}(B) = 8.

  • 进行操作 i = 2。现在, A = (5,1,2,4,3), B = (3,2,1,5,4).
  • 进行操作 i = 1。现在, A = (1,5,2,4,3), B = (2,3,1,5,4).
  • 进行操作 i = 4。现在, A = (1,5,2,3,4), B = (2,3,1,4,5).

在这里, A 具有最长的递增子序列 (1,2,3,4),所以 \mathrm{LIS}(A)=4,和 B 具有最长的递增子序列 (2,3,4,5),所以 \mathrm{LIS}(B)=4.


示例输入 2

5
1 2 3 4 5
1 2 3 4 5

示例输出 2

10

您可以决定根本不执行该操作来实现 \mathrm{LIS}(A) + \mathrm{LIS}(B) = 10.