Maximize Sum of Mex

AtCoder

IDarc204_c

Time2000ms

Memory256MB

Difficulty—

You are given a positive integer $N$ and a permutation $P = (P_{1}, P_{2}, \dots, P_{N})$ of $(1, 2, \dots , N)$. Process $Q$ queries. In each query, non-negative integers $A_{0}, A_{1}, A_{2}$ are given, so output the answer to the following problem. It is guaranteed that $A_{0} + A_{1} + A_{2} = N$. > A sequence $B$ of length $N$ is called a **good sequence** if and only if it satisfies all of the following conditions: > > * There are exactly $A_{0}$ integers $i$ with $1 \leq i \leq N$ such that $B_{i} = 0$. > * There are exactly $A_{1}$ integers $i$ with $1 \leq i \leq N$ such that $B_{i} = 1$. > * There are exactly $A_{2}$ integers $i$ with $1 \leq i \leq N$ such that $B_{i} = 2$. > > For a sequence $B$ of length $N$, the **score** is defined as follows: > > * $\displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})$ > > Here, $\mathrm{MEX}(x, y)$ is defined as the minimum non-negative integer that is neither $x$ nor $y$. > Find the maximum value of the **score** over all **good sequences**. ## Constraints * $1\leq N\leq 3\times 10^{5}$ * $(P_{1}, P_{2}, \dots , P_{N})$ is a permutation of $(1, 2, \dots , N)$. * $1\leq Q\leq 3\times 10^{5}$ * $0\leq A_{i}$ * For each query, $A_{0} + A_{1} + A_{2} = N$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $P_{1}$ $P_{2}$ $\dots$ $P_{N}$ $Q$ $query_{1}$ $query_{2}$ $\cdots$ $query_{Q}$ Here $query_{i}$ is the $i$\-th query, given in the following format: $A_{0}$ $A_{1}$ $A_{2}$ [samples]

Samples

Input #1

Output #1

3
2

For the first query, $B = (0, 1, 2)$ is a good sequence. The score of this sequence is $\mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3$, which is $3$. There is no good sequence with a score greater than $3$, so output $3$ on the first line.

Input #2

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

Output #2

Input #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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Maximize Sum of Mex",
    "description": {
      "content": "You are given a positive integer $N$ and a permutation $P = (P_{1}, P_{2}, \\dots, P_{N})$ of $(1, 2, \\dots , N)$. Process $Q$ queries. In each query, non-negative integers $A_{0}, A_{1}, A_{2}$ are gi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc204_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $N$ and a permutation $P = (P_{1}, P_{2}, \\dots, P_{N})$ of $(1, 2, \\dots , N)$.\nProcess $Q$ queries. In each query, non-negative integers $A_{0}, A_{1}, A_{2}$ are gi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments