P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2

有 $2N$ 张卡牌从左到右依次放在桌子上，编号为 $1,2,\ldots,2N$，卡牌 $i$ 上写有整数 $A_i$。对于 $x=1,2,\ldots,N$，存在恰好两张卡牌上写的整数为 $x$。 海狸比太郎决定用这些卡牌玩一个叫做“神经衰弱”的游戏；该游戏的流程如下： - 依次考虑卡牌 $i=1,2,\ldots,2N$： 1. 比太郎决定是否拿起这张卡牌：如果他决定拿起，那么依次进行以下的步骤 2 至步骤 5；如果他决定不拿起（跳过该卡牌），则跳过以下的步骤； 2. 如果比太郎的手中持有一张写有 $A_i$ 的卡牌，那么该卡牌和卡牌 $i$ 同时消失，他获得 $V_{A_i}$ 分； 3. 如果比太郎左手中有一张卡牌，那么他将其丢弃； 4. 如果比太郎右手中有一张卡牌，那么他将其转移到左手； 5. 如果卡牌 $i$ 没有在步骤 2 中消失，那么他将其放在右手中。 通过上面的流程，每次得到的分数之和即为比太郎的最终得分。 请求出比太郎能获得的最大得分。

无

无

#### 【样例解释 #1】 比太郎可以通过以下流程获得分数 $13$： 1. 拿起卡牌 $1$，该卡牌上面写着 $1$；由于比太郎没有其他写着 $1$ 的纸牌，所以他将其放在右手中； 2. 跳过卡牌 $2$； 3. 拿起卡牌 $3$，该卡牌上面写着 $3$；由于比太郎没有其他写着 $3$ 的纸牌，所以卡牌 $1$ 从右手转移到了左手，他将卡牌 $3$ 放在右手中； 4. 拿起卡牌 $4$，该卡牌上面写着 $1$；由于卡牌 $1$ 上也写着 $1$，所以两张牌都消失了，他获得 $V_1=5$ 分，卡牌 $3$ 则从右手转移到了左手； 5. 跳过卡牌 $5$； 6. 拿起卡牌 $6$，该卡牌上面写着 $3$；由于卡牌 $3$ 上也写着 $3$，所以两张牌都消失了，他获得 $V_3=8$ 分，此时他两只手上都没有任何卡牌了。 可以证明这是最优的。 该样例满足子任务 $1,2,3,4,5,6,8,9$ 的限制。 #### 【样例解释 #2】 比太郎可以通过拿起卡牌 $1,2,3,4,5,6,8$ 来获得分数 $V_1+V_2+V_3=156$。可以证明这是最优的。 该样例满足子任务 $3,4,5,6,8,9$ 的限制。 #### 【样例解释 #3】 该样例满足子任务 $4,5,6,8,9$ 的限制。 #### 【样例解释 #4】 该样例满足子任务 $4,5,6,7,8,9$ 的限制。 #### 【数据范围】 - $1\le N\le 4\times 10^5$； - $A_1,A_2,\ldots,A_{2N}$ 中，对于 $x=1,2,\ldots,N$，$x$ 正好出现两次； - $1\le V_k\le 10^9$。 #### 【子任务】 1. （$8$ 分）$(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)$，$N\le 5000$； 2. （$12$ 分）$(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)$； 3. （$6$ 分）$N\le 9$； 4. （$9$ 分）$N\le 18$； 5. （$16$ 分）$N\le 300$ 6. （$18$ 分）$N\le 3000$； 7. （$18$ 分）$N\le 1.5\times 10^5$，$V_k\le 1(1\le k\le N)$； 8. （$8$ 分）$N\le 1.5\times 10^5$； 9. （$5$ 分）无附加限制。