2193C.md (2032B)
1 Source: https://codeforces.com/problemset/problem/2193/C 2 3 C. Replace and Sum 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 Today, KQ has an exam at the Grail Academy. A strict teacher gave a task that KQ could not solve. He was given two arrays $a$ and $b$ of length $n$. KQ is allowed to perform the following operations on the arrays: 22 23 * Choose an index $i$ ($1\le i\lt n$) and replace $a_i$ with $a_{i+1}$. 24 * Choose an index $i$ ($1\le i\le n$) and replace $a_i$ with $b_i$. 25 26 Now he has $q$ queries. Each query is described by two numbers $l$ and $r$. His task is to find the maximum value of the sum $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ for each query, if he can perform any number of operations on any elements of the array. Since he is not skilled enough for this, he asks for your help. 27 28 Input 29 30 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. The description of the test cases follows. 31 32 The first line of each test case contains two integers $n$, $q$ $(1\le n, q\le 2 \cdot 10^5)$. 33 34 The second line of each test case contains $n$ integers $a_1, a_2,...,a_n$ $(1\le a_i\le 10^4)$. 35 36 The third line of each test case contains $n$ integers $b_1, b_2,...,b_n$ $(1\le b_i\le 10^4)$. 37 38 The following $q$ lines contain two integers $l$ and $r$ $(1\le l\le r\le n)$. 39 40 It is guaranteed that the sum of the values of $n$ and the sum of the values of $q$ across all test cases do not exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test case, output $q$ numbers separated by spaces — the maximum values of the sums $(a_l + a_{l+1} + a_{l+2} + \dots + a_r)$. 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 3 1 54 55 3 2 1 56 57 1 2 3 58 59 1 3 60 61 1 1 62 63 1 64 65 2 66 67 1 1 68 69 3 2 70 71 6 7 5 72 73 9 6 8 74 75 1 2 76 77 2 3 78 79 4 3 80 81 4 3 2 1 82 83 5 1 3 1 84 85 1 2 86 87 2 4 88 89 3 4 90 ``` 91 92 Output 93 94 ``` 95 9 96 97 2 98 99 17 16 100 101 8 7 4 102 ``` 103 104 Note 105 106 Consider the first test case. Replace $a_3$ with $b_3$, $a = [3, 2, 3]$. Replace $a_2$ with $a_3$, $a = [3, 3, 3]$. The sum $a_1 + a_2 + a_3 = 9$.