← 返回题目列表

AtCoder · arc204_c

C. 最大化 Mex 之和

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

分数: 900 点

问题陈述

给你一个正整数 N 和排列 P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots , N).

流程 Q 查询。在每个查询中,非负整数 给出了 A_{0}, A_{1}, A_{2} ,因此输出以下问题的答案。可以保证 A_{0} + A_{1} + A_{2} = N.

一个序列 B 长度 N 被称为 好的序列 当且仅当满足以下所有条件时:

  • 正好有 A_{0} 整数 i 与 1 \leq i \leq N 这样 B_{i} = 0.
  • 正好有 A_{1} 整数 i 与 1 \leq i \leq N 这样 B_{i} = 1.
  • 正好有 A_{2} 整数 i 与 1 \leq i \leq N 这样 B_{i} = 2.

对于序列 B 长度 N, 分数 游戏的 定义如下:

  • \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})

在这里, \mathrm{MEX}(x, y) 被定义为既不是的最小非负整数 x 也不 y.

找到最大值 分数 游戏的 总的来说 好的序列.

约束

  • 1\leq N\leq 3\times 10^{5}
  • (P_{1}, P_{2}, \dots , P_{N}) 是一个排列 (1, 2, \dots , N).
  • 1\leq Q\leq 3\times 10^{5}
  • 0\leq A_{i}
  • 对于每个查询, A_{0} + A_{1} + A_{2} = N.
  • 所有输入值均为整数。

输入

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

N
P_{1} P_{2} \dots P_{N}
Q
query_{1}
query_{2}
\cdots
query_{Q}

这里 query_{i} 是 i-第一个查询,按以下格式给出:

A_{0} A_{1} A_{2}

输出

输出 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

3
2 3 1
2
1 1 1
1 0 2

示例输出 1

3
2

对于第一个查询, B = (0, 1, 2) 是一个很好的序列。该序列的得分为 \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3,即 3。不存在分数大于的好序列 3,所以输出 3 在第一行。


示例输入 2

7
6 3 4 5 2 1 7
4
2 2 3
4 1 2
0 3 4
1 2 4

示例输出 2

8
9
0
4

示例输入 3

9
1 6 7 3 5 8 9 2 4
10
5 3 1
0 7 2
0 6 3
1 3 5
4 0 5
4 2 3
1 5 3
4 5 0
2 2 5
2 5 2

示例输出 3

14
0
0
4
7
11
4
13
8
8