codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2086C.md (3293B)


      1 Source: https://codeforces.com/problemset/problem/2086/C
      2 
      3 C. Disappearing Permutation
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A permutation of integers from $1$ to $n$ is an array of size $n$ where each integer from $1$ to $n$ appears exactly once.
     22 
     23 You are given a permutation $p$ of integers from $1$ to $n$. You have to process $n$ queries. During the $i$-th query, you replace $p_{d_i}$ with $0$. Each element is replaced with $0$ exactly once. The changes made in the queries are saved, that is, after the $i$-th query, all integers $p_{d_1}, p_{d_2}, \dots, p_{d_i}$ are zeroes.
     24 
     25 After each query, you have to find the minimum number of operations required to fix the array; in other words, to transform the current array into any permutation of integers from $1$ to $n$ (possibly into the original permutation $p$, possibly into some other permutation).
     26 
     27 The operation you can perform to fix the array is the following one:
     28 
     29 * choose the integer $i$ from $1$ to $n$, replace the $i$-th element of the array with $i$.
     30 
     31 Note that the answer for each query is calculated independently, meaning you do not actually apply any operations, just calculate the minimum number of operations.
     32 
     33 Input
     34 
     35 Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. Then the test cases follow.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{5}$).
     38 
     39 The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_{i} \le n$) — the original permutation. All $p_i$ are distinct.
     40 
     41 The third line of each test case contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_{i} \le n$). All $d_{i}$ are distinct.
     42 
     43 Additional constraint on the input:
     44 
     45 * the sum of $n$ across all test cases does not exceed $2 \cdot 10^{5}$.
     46 
     47 Output
     48 
     49 For each test case, output a line containing $n$ integers, where the $i$-th integer should be equal to the minimum number of operations required to fix the array which was obtained after the $i$-th query (i.e., the permutation $p$ where all integers $p_{d_1}, p_{d_2}, \dots, p_{d_i}$ are replaced by zeroes).
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 3
     57 
     58 3
     59 
     60 1 2 3
     61 
     62 3 2 1
     63 
     64 5
     65 
     66 4 5 3 1 2
     67 
     68 4 5 1 3 2
     69 
     70 7
     71 
     72 4 3 1 2 7 5 6
     73 
     74 1 2 3 4 5 6 7
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 1 2 3 
     81 2 4 4 5 5 
     82 4 4 4 4 7 7 7
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, after each query, every integer which was replaced by $0$ can be restored by one operation.
     88 
     89 In the second test case, you can act as follows:
     90 
     91 * Query $1$: $p = [4, 5, 3, 0, 2]$, it can be transformed into $[{\color{red}1}, 5, 3, {\color{red}4}, 2]$.
     92 * Query $2$: $p = [4, 5, 3, 0, 0]$, it can be transformed into $[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$.
     93 * Query $3$: $p = [0, 5, 3, 0, 0]$, it can be transformed into $[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$.
     94 * Query $4$: $p = [0, 5, 0, 0, 0]$, it can be transformed into $[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$.
     95 * Query $5$: $p = [0, 0, 0, 0, 0]$, it can be transformed into $[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$.
     96 
     97 The numbers that were changed are highlighted in red.