2063B.md (2378B)
1 Source: https://codeforces.com/problemset/problem/2063/B 2 3 B. Subsequence Update 4 5 time limit per test 6 7 1.5 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 After Little John borrowed expansion screws from auntie a few hundred times, eventually she decided to come and take back the unused ones. 22 23 But as they are a crucial part of home design, Little John decides to hide some in the most unreachable places — under the eco-friendly wood veneers. 24 25 26 27 You are given an integer sequence $a_1, a_2, \ldots, a_n$, and a segment $[l,r]$ ($1 \le l \le r \le n$). 28 29 You must perform the following operation on the sequence exactly once. 30 31 * Choose any subsequence$^{\text{∗}}$ of the sequence $a$, and reverse it. Note that the subsequence does not have to be contiguous. 32 33 Formally, choose any number of indices $i_1,i_2,\ldots,i_k$ such that $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$. Then, change the $i_x$-th element to the original value of the $i_{k-x+1}$-th element simultaneously for all $1 \le x \le k$. 34 35 Find the minimum value of $a_l+a_{l+1}+\ldots+a_{r-1}+a_r$ after performing the operation. 36 37 $^{\text{∗}}$A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) element from arbitrary positions. 38 39 Input 40 41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 42 43 The first line of each test case contains three integers $n$, $l$, $r$ ($1 \le l \le r \le n \le 10^5$) — the length of $a$, and the segment $[l,r]$. 44 45 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_{i} \le 10^9$). 46 47 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 48 49 Output 50 51 For each test case, output the minimum value of $a_l+a_{l+1}+\ldots+a_{r-1}+a_r$ on a separate line. 52 53 Example 54 55 Input 56 57 ``` 58 6 59 60 2 1 1 61 62 2 1 63 64 3 2 3 65 66 1 2 3 67 68 3 1 3 69 70 3 1 2 71 72 4 2 3 73 74 1 2 2 2 75 76 5 2 5 77 78 3 3 2 3 5 79 80 6 1 3 81 82 3 6 6 4 3 2 83 ``` 84 85 Output 86 87 ``` 88 1 89 3 90 6 91 3 92 11 93 8 94 ``` 95 96 Note 97 98 On the second test case, the array is $a=[1,2,3]$ and the segment is $[2,3]$. 99 100 After choosing the subsequence $a_1,a_3$ and reversing it, the sequence becomes $[3,2,1]$. Then, the sum $a_2+a_3$ becomes $3$. It can be shown that the minimum possible value of the sum is $3$.