P16059 [CSPro 24] Sequence Query

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

In the shopping mall on Xixi Aifu Island, there are many stores and a wide variety of products. To help visitors quickly choose the product they want within their budget, the IT department decides to develop a product retrieval system. For any given budget $x$, it should query the most expensive product whose price is within the budget range ($\leq x$). If no product meets the budget requirement, it will recommend a customized souvenir from Xixi Aifu Island that can be collected for free. Assume there are $n$ products in the mall, and their prices from low to high are $A_1, A_2 \cdots A_n$. Then the process of retrieving a product based on budget $x$ can be abstracted as the following sequence query problem. $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$. (This definition implies that $n$ must be less than $N$.) Based on the sequence $A$, for any integer $x$ in the range $[0, N)$, define the query $f(x)$ as: the **index of the largest** integer in sequence $A$ that is **less than or equal to** $x$. Specifically, there are two cases: 1. There exists an index $0 \leq i < n$ such that $A_i \leq x < A_{i+1}$. In this case, all numbers in $A$ from $A_0$ to $A_i$ are less than or equal to $x$. The largest is $A_i$, whose index is $i$, so $f(x) = i$. 2. $A_n \leq x$. In this case, all numbers in $A$ are less than or equal to $x$. The largest is $A_n$, so $f(x) = n$. Let $sum(A)$ denote the sum of $f(0)$ to $f(N - 1)$, that is: $$ \begin{aligned} sum(A) = \sum_{i=0}^{N-1} f(i) = f(0) + f(1) + f(2) + \cdots + f(N - 1) \end{aligned} $$ Given the sequence $A$, compute $sum(A)$.

Read input 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$.

Write output to standard output.

### Sample 1 Explanation $A = [0, 2, 5, 8]$ | $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $f(i)$ | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | As shown in the table above, $sum(A) = f(0) + f(1) + \cdots + f(9) = 15$. Considering that $f(0) = f(1)$, $f(2) = f(3) = f(4)$, $f(5) = f(6) = f(7)$, and $f(8) = f(9)$, you can also compute $sum(A)$ using the following expression: $$ \begin{aligned} sum(A) = f(0) \times 2 + f(2) \times 3 + f(5) \times 3 + f(8) \times 2 \end{aligned} $$ ### Subtasks $50\%$ of the testdata satisfy $1 \leq n \leq 200$ and $n < N \leq 1000$; all testdata satisfy $1 \leq n \leq 200$ and $n < N \leq 10^7$. ### Hint If there exists an interval $[i, j)$ such that $f(i) = f(i+1) = \cdots = f(j-1)$, using multiplication $f(i) \times (j - i)$ instead of adding $f(i)$ to $f(j-1)$ one by one may greatly improve the algorithm efficiency. Translated by ChatGPT 5