30852번 - Apricot Seeds 다국어

Sam has some apricot seeds, and he wants to sort them in non-decreasing order based on size. He uses a unique method to sort the apricot seeds, described as follows:

Given $n$ apricot seeds, Sam performs a total of $n - 1$ steps to sort them. For each step $k$ from $1$ to $n - 1$:

• He compares the first seed with the second seed. If the second seed is smaller, he swaps their positions.
• He then compares the second seed with the third seed. If the third seed is smaller, he swaps their positions.
• He continues this process until he compares the $(n - k)$-th seed with the $(n - k + 1)$-th seed and swaps their positions if the $(n - k + 1)$-th seed is smaller.

Sam's friend Tom quickly realizes that this is the famous bubble sorting algorithm. To illustrate the inefficiency of this algorithm to Sam, Tom decides to ask Sam $q$ questions. A question is represented as a tuple $[s, e, m, l, r]$. For given a sequence of $n$ seeds, each question $[s, e, m, l, r]$ asks for the sum of the sizes of seeds from position $l$ to $r$ of the (partially) sorted subsequence after applying the first $m$ steps of Sam's method to the subsequence of seeds from position $s$ to $e$ of the initial sequence.

For instance, consider four ($n = 4$) seeds with sizes of $(1,3,4,2)$ and two ($q = 2$) questions $[2,4,1,2,2]$ and $[1,4,2,3,4]$. For the first question, the subsequence of the sizes from the second ($s = 2$) seed to the fourth ($e = 4$) seed is $(3,4,2)$. After applying one step ($m = 1$) of Sam’s method, it becomes $(3,2,4)$. The sum of the sizes of seeds from the second position ($l = 2$) to the second position ($r = 2$) in this (partially) sorted subsequence is $2$. For the second question, the subsequence is $(1,3,4,2)$. After applying two steps, it becomes $(1,2,3,4)$. The sum of the sizes of seeds from position $3$ to $4$ in this (partially) sorted sequence is $3 + 4 = 7$.

Given a sequence of $n$ seeds and $q$ questions, write a program that computes the answer for each question.

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $q$ ($2 ≤ n ≤ 1\,000\,000$, $1 ≤ q ≤ 500\,000$), where $n$ represents the number of seeds and $q$ represents the number of questions. The second line contains $n$ integers, separated by spaces, representing the sizes of the apricot seeds in their initial order. Each size is between $1$ and $10^9$, both inclusive. Each of the next $q$ lines contains five positive integers $s$, $e$, $m$, $l$, $r$ of query $[s, e, m, l, r]$, separated by spaces, representing a question, where $1 ≤ s < e ≤ n$, $1 ≤ m ≤ e - s$, and $1 ≤ l ≤ r ≤ e - s + 1$.

Your program is to write to standard output. For each of the $q$ questions, output one line with the answer. The answer for a question $[s, e, m, l, r]$ is the sum of the sizes of seeds from position $l$ to $r$ of the partially sorted subsequence after applying the first $m$ steps of Sam's method to the subsequence of seeds from position $s$ to $e$ of the input sequence.