P14085 [ICPC 2023 Seoul R] Apricot Seeds

Sam 有一些杏核，他想按照杏核的大小将它们按非递减顺序排序。他使用了一种独特的方法来对杏核排序，具体过程如下： 给定 $n$ 个杏核，Sam 总共进行 $n-1$ 步排序。对于每一步 $k$（$1 \leq k \leq n-1$）： - 他比较第一个杏核和第二个杏核。如果第二个比第一个小，则交换它们的位置。 - 然后他比较第二个和第三个杏核。如果第三个比第二个小，则交换它们的位置。 - 按此方式依次继续，直到比较第 $(n-k)$ 个杏核和第 $(n-k+1)$ 个杏核，如果第 $(n-k+1)$ 个比前一个小，则交换它们的位置。 Sam 的朋友 Tom 很快发现这就是著名的冒泡排序算法。为了向 Sam 展示这种方法的低效性，Tom 决定向 Sam 提出 $q$ 个问题。每个问题以 $[s,e,m,l,r]$ 的五元组表示。 对于长度为 $n$ 的初始杏核序列，每个问题 $[s,e,m,l,r]$ 是这样定义的：首先取下标从 $s$ 到 $e$ 的子序列，对它进行 Sam 方法的前 $m$ 步操作，操作后得到一个（部分）排序的子序列，然后取该子序列中第 $l$ 个到第 $r$ 个杏核的大小，并输出这些大小的和。 例如，考虑 4 个（$n=4$）杏核，大小为 $(1,3,4,2)$，以及两个（$q=2$）问题 $[2,4,1,2,2]$ 和 $[1,4,2,3,4]$。第一个问题，取第 2 个到第 4 个（$s=2,e=4$）得到序列 $(3,4,2)$。对其进行 1 步 Sam 的方法后，序列变为 $(3,2,4)$，再取该序列的第 2 个到第 2 个（$l=2,r=2$），得到大小为 $2$。第二个问题，取原序列 $(1,3,4,2)$，进行 2 步操作后为 $(1,2,3,4)$，取第 3 个到第 4 个，大小和为 $3+4=7$。 现在，给定 $n$ 个杏核的初始序列和 $q$ 个问题，请你计算每个问题的答案。

你的程序需要从标准输入读取数据。第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 1\,000\,000,\, 1 \leq q \leq 500\,000$），分别表示杏核数量和问题数量。第二行有 $n$ 个用空格分隔的整数，表示杏核的初始大小，每个大小在 $1$ 到 $10^9$ 之间。接下来的 $q$ 行，每行包含五个正整数 $s,e,m,l,r$，分别描述一个问题 $[s,e,m,l,r]$，其中 $1 \leq s < e \leq n,\ 1 \leq m \leq e-s,\ 1 \leq l \leq r \leq e-s+1$。

对于每个问题，输出一行表示答案。每行输出一个整数，即按照题目要求排序后的子序列的第 $l$ 到 $r$ 个（包含）杏核的大小和。

由 ChatGPT 5 翻译