P14085 [ICPC 2023 Seoul R] 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 𝑠 to 𝑒 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 \le n\le 1,000,000, 1 \le q \le 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 \le s

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.