codeforces-scrape

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

1789C.md (2944B)


      1 Source: https://codeforces.com/problemset/problem/1789/C
      2 
      3 C. Serval and Toxel's Arrays
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Toxel likes arrays. Before traveling to the Paldea region, Serval gave him an array $a$ as a gift. This array has $n$ pairwise distinct elements.
     22 
     23 In order to get more arrays, Toxel performed $m$ operations with the initial array. In the $i$-th operation, he modified the $p_{i}$-th element of the $(i-1)$-th array to $v_{i}$, resulting in the $i$-th array (the initial array $a$ is numbered as $0$). During modifications, Toxel guaranteed that the elements of each array are still pairwise distinct after each operation.
     24 
     25 Finally, Toxel got $m+1$ arrays and denoted them as $A_{0}=a, A_{1},\ldots,A_{m}$. For each pair $(i,j)$ ($0\le i \lt j\le m$), Toxel defines its value as the number of distinct elements of the concatenation of $A_{i}$ and $A_{j}$. Now Toxel wonders, what is the sum of the values of all pairs? Please help him to calculate the answer.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^{4}$). The description of the test cases follows.
     30 
     31 The first line of each test case contains two integers $n$ and $m$ ($1\le n,m\le2\cdot10^{5}$) — the length of the array and the number of operations.
     32 
     33 The second line of each test case contains $n$ integers $a_{1},a_{2},\dots,a_{n}$ ($1\le a_{i}\le n+m$). It is guaranteed that all $a_i$ are pairwise distinct.
     34 
     35 Each of the next $m$ lines of each test case contains two integers $p_{i}$ and $v_{i}$ ($1\le p_{i}\le n$, $1\le v_{i}\le n+m$) — the position of the modified element and its new value. It is guaranteed that the elements of each array are still pairwise distinct after each modification.
     36 
     37 It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot10^{5}$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the sum of the values of all pairs of arrays.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 3 2
     51 
     52 1 2 3
     53 
     54 1 4
     55 
     56 2 5
     57 
     58 1 1
     59 
     60 1
     61 
     62 1 1
     63 
     64 10 10
     65 
     66 4 6 9 12 16 20 2 10 19 7
     67 
     68 1 3
     69 
     70 5 4
     71 
     72 2 17
     73 
     74 2 18
     75 
     76 6 11
     77 
     78 7 1
     79 
     80 8 17
     81 
     82 5 5
     83 
     84 5 5
     85 
     86 2 2
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 13
     93 1
     94 705
     95 ```
     96 
     97 Note
     98 
     99 In the first test case, the arrays change as follows: $[1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]$.
    100 
    101 The concatenation of the $0$-th array and the $1$-st array is $\require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]$. There are $4$ distinct elements.
    102 
    103 The concatenation of the $0$-th array and the $2$-nd array is $\require{cancel}[1,2,3,4,5,\cancel{3}]$. There are $5$ distinct elements.
    104 
    105 The concatenation of the $1$-st array and the $2$-nd array is $\require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]$. There are $4$ distinct elements.
    106 
    107 Strikethrough elements are duplicates in the array.
    108 
    109 Therefore, the answer is $4+5+4=13$.
    110 
    111 In the second test case, note that the array may remain unchanged after operations.