1609.md (3234B)
1 Source: https://codeforces.com/blog/entry/97350 2 3 Tutorial is loading... 4 5 **Prepared by** [Vladik](/profile/Vladik "Master Vladik"). 6 **Solution:** [137274527](/contest/1609/submission/137274527 "Submission 137274527 by Vladik") 7 8 Tutorial is loading... 9 10 **Prepared by** [AleXman111](/profile/AleXman111 "Candidate Master AleXman111"). 11 **Solution:** [137274647](/contest/1609/submission/137274647 "Submission 137274647 by Vladik") 12 13 Tutorial is loading... 14 15 **Prepared by** [AleXman111](/profile/AleXman111 "Candidate Master AleXman111"). 16 **Solution:** [137274769](/contest/1609/submission/137274769 "Submission 137274769 by Vladik") 17 18 Tutorial is loading... 19 20 **Prepared by** [4llower](/profile/4llower "Candidate Master 4llower"). 21 **Solution with** $O(n \cdot log(n))$: [137274837](/contest/1609/submission/137274837 "Submission 137274837 by Vladik") 22 23 Tutorial is loading... 24 25 **Prepared by** [AleXman111](/profile/AleXman111 "Candidate Master AleXman111"). 26 **Solution:** [137274954](/contest/1609/submission/137274954 "Submission 137274954 by Vladik") 27 28 Tutorial is loading... 29 30 [1609G - A Stroll Around the Matrix](/contest/1609/problem/G) 31 32 Let's try to solve the problem without asking for changes. Note that in the matrix constructed in this way for the move from (i, j) it is always profitable to go to the cell with the smallest number. This can be seen more clearly in the matrix of the first test case: 33 34  35 36 This allows you to solve the problem with complexity $O(n + m)$, but this is not enough for a complete solution. Let's introduce two new arrays of the difference between the adjacent elements of the arrays $da_i = a_{i + 1} - a_i$ and $db_i = b_{i + 1} - b_i$. 37 38 Note that our greedy decision turns right out of the cell $(i, j)$, when $da_i \gt db_j$. For clarity, below is an illustration of the turns: 39 40  41 42 Each time such a turn to the right in the cell $(i, j)$ decreases our total sum by $(da_i - db_j) + (da_{i + 1} - db_j) + \dots + (da_{n - 1} - db_j) = (\sum_{t=i}^{n - 1} da_t) - db_j \cdot (n - i)$. Which is actually equivalent to the sum of $da_i - db_j$ for all $da_i \gt db_j$. 43 44 Such a sum can be considered by recognizing for each $i$ by a binary search the last $db_j$ for which the expression $da_i \gt db_j$ is true. This allows us to solve the problem in $O(n \cdot log(m))$ using the prefix sums of the $db$ array. 45 46 Now let's get back to change requests. Because the size of the $da$ array is small enough, then we can change the values of its elements by a simple. To store the $db$ array, you will need to use a segment tree supporting the following operations: 47 - Adding a number at the suffix (since we are working with an array $db$, not $b$, then all elements will change by one number equal to the step of the arithmetic progression). 48 - Sum of array numbers on array prefix so far $element_i \lt X$. ($da_i$ will act as $X$). 49 50 **Prepared by** [Vladik](/profile/Vladik "Master Vladik"). 51 **Total complexity:** $O(q \cdot n \cdot log(m))$. 52 53 Tutorial is loading... 54 55 **Prepared by** [budalnik](/profile/budalnik "International Grandmaster budalnik").