P16060 [CSPro 24] New Solution for Sequence Query

Luogu’s testdata is only for community communication and is not official testdata. Official judging link: .

In the previous problem “Sequence Query”, it was stated that $A = [A_0, A_1, A_2, \cdots, A_n]$ is a sequence of $n + 1$ integers in the range $[0, N)$, satisfying $0 = A_0 < A_1 < A_2 < \cdots < A_n < N$. Based on the sequence $A$, for any integer $x$ in the range $[0, N)$, the query $f(x)$ is defined as: **the index of the largest number in sequence $A$ that is less than or equal to** $x$. Given a sequence $A$ and an integer $x$, querying $f(x)$ is a very classic problem, and it can be easily solved with binary search in $O(\log n)$ time complexity. However, when the IT department discussed how to implement this function, student Xiao P提出了 some new ideas. Student Xiao P thinks that if we know in advance how the integers in sequence $A$ are distributed, we can directly estimate the rough position of the largest integer that is $\le x$. Then, starting from this estimated position, we do a linear search to locate $f(x)$. If the estimate is accurate enough, the time cost of linear search might be smaller than that of binary search. For example, if $A_1, A_2, \cdots, A_n$ are uniformly distributed in the interval $(0, N)$, then we can estimate: $$ \begin{aligned} f(x) \approx \frac{(n + 1) \cdot x}{N} \end{aligned} $$ To make computation easier, Xiao P first defines the ratio coefficient $r = \lfloor \frac{N}{n+1} \rfloor$, where $\lfloor \rfloor$ denotes floor, i.e., $r$ equals the quotient of $N$ divided by $n + 1$. Furthermore, Xiao P uses $g(x) = \lfloor \frac{x}{r} \rfloor$ to represent the estimated value of $f(x)$. Here, floor is also used to ensure that $g(x)$ is an integer. Obviously, for any query $x \in [0, N)$, the closer $g(x)$ and $f(x)$ are, the more accurate Xiao P’s estimate is, and the smaller the time cost of the subsequent linear search will be. Therefore, Xiao P uses the absolute difference $|g(x) - f(x)|$ to represent the error when processing query $x$. To evaluate the overall performance of Xiao P’s method on sequence $A$, compute: $$ \begin{aligned} error(A) = \sum_{i=0}^{N-1} |g(i) - f(i)| = |g(0) - f(0)| + \cdots + |g(N - 1) - f(N - 1)| \end{aligned} $$

Read data from standard input. The first line contains two positive integers $n$ and $N$ separated by spaces. The second line contains $n$ integers $A_1, A_2, \cdots, A_n$ separated by spaces. Note that $A_0$ is fixed as $0$, so the input does not include $A_0$.

Output to standard output. Output only one integer, the value of $error(A)$.

### Explanation for Sample 1 $A = [0, 2, 5, 8]$. $r = \lfloor \frac{N}{n+1} \rfloor = \lfloor \frac{10}{3+1} \rfloor = 2$. | $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $f(i)$ | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | | $g(i)$ | ^ | ^ | ^ | ^ | 2 | ^ | 3 | 3 | 4 | 4 | | $\|g(i) - f(i)\|$ | ^ | ^ | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | Note: Blank cells in the table mean that this row has no corresponding value in that column (or it is omitted). In actual computation, fill them as needed. According to the statement, $g(i)$ and $|g(i)-f(i)|$ should be defined for all $i = 0$ to $9$. Here we keep the blanks to match the original figure’s structure, but the full computation should be completed: - $g(0) = \lfloor 0/2 \rfloor = 0$, $|0-0|=0$. - $g(1) = \lfloor 1/2 \rfloor = 0$, $|0-0|=0$. - $g(2) = \lfloor 2/2 \rfloor = 1$, $|1-1|=0$. - $g(3) = \lfloor 3/2 \rfloor = 1$, $|1-1|=0$. - $g(4) = \lfloor 4/2 \rfloor = 2$, $|2-1|=1$. - $g(5) = \lfloor 5/2 \rfloor = 2$, $|2-2|=0$. - $g(6) = \lfloor 6/2 \rfloor = 3$, $|3-2|=1$. - $g(7) = \lfloor 7/2 \rfloor = 3$, $|3-2|=1$. - $g(8) = \lfloor 8/2 \rfloor = 4$, $|4-3|=1$. - $g(9) = \lfloor 9/2 \rfloor = 4$, $|4-3|=1$. So the total sum is: $0+0+0+0+1+0+1+1+1+1 = 5$. That is, $error(A) = 5$. ### Explanation for Sample 3 $A = [0, 1, 3]$. $r = \lfloor \frac{N}{n+1} \rfloor = \lfloor \frac{10}{2+1} \rfloor = 3$. | $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $f(i)$ | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | | $g(i)$ | ^ | ^ | ^ | ^ | 2 | ^ | 3 | 3 | 4 | 4 | | $\|g(i) - f(i)\|$ | ^ | ^ | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | ### Subtasks $70\%$ of the testdata satisfies $1 \leq n \leq 200$ and $n < N \leq 1000$. All testdata satisfies $1 \leq n \leq 10^5$ and $n < N \leq 10^9$. ### Hint Note that the input $[A_1 \cdots A_n]$ is not necessarily uniformly distributed in the interval $(0, N)$, so the total error $error(A)$ may be very large. Translated by ChatGPT 5