1485B.md (1617B)
1 Source: https://codeforces.com/problemset/problem/1485/B 2 3 B. Replace and Keep Sorted 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 Given a positive integer $k$, two arrays are called $k$-similar if: 22 23 * they are strictly increasing; 24 * they have the same length; 25 * all their elements are positive integers between $1$ and $k$ (inclusive); 26 * they differ in exactly one position. 27 28 You are given an integer $k$, a strictly increasing array $a$ and $q$ queries. For each query, you are given two integers $l_i \leq r_i$. Your task is to find how many arrays $b$ exist, such that $b$ is $k$-similar to array $[a_{l_i},a_{l_i+1}\ldots,a_{r_i}]$. 29 30 Input 31 32 The first line contains three integers $n$, $q$ and $k$ ($1\leq n, q \leq 10^5$, $n\leq k \leq 10^9$) — the length of array $a$, the number of queries and number $k$. 33 34 The second line contains $n$ integers $a_1, a_2, \ldots,a_n$ ($1 \leq a_i \leq k$). This array is strictly increasing — $a_1 \lt a_2 \lt \ldots \lt a_n$. 35 36 Each of the following $q$ lines contains two integers $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$). 37 38 Output 39 40 Print $q$ lines. The $i$-th of them should contain the answer to the $i$-th query. 41 42 Examples 43 44 Input 45 46 ``` 47 4 2 5 48 1 2 4 5 49 2 3 50 3 4 51 ``` 52 53 Output 54 55 ``` 56 4 57 3 58 ``` 59 60 Input 61 62 ``` 63 6 5 10 64 2 4 6 7 8 9 65 1 4 66 1 2 67 3 5 68 1 6 69 5 5 70 ``` 71 72 Output 73 74 ``` 75 8 76 9 77 7 78 6 79 9 80 ``` 81 82 Note 83 84 In the first example: 85 86 In the first query there are $4$ arrays that are $5$-similar to $[2,4]$: $[1,4],[3,4],[2,3],[2,5]$. 87 88 In the second query there are $3$ arrays that are $5$-similar to $[4,5]$: $[1,5],[2,5],[3,5]$.