#P12892. 【NOIP Round #7】冒泡排序

    ID: 12078 传统题 文件IO:sort 4000ms 1024MiB 尝试: 85 已通过: 13 难度: 8 上传者: 标签>CF2400提高+/省选-冒泡排序离散化可持久化线段树路径复制前缀版本作差线段树上二分

【NOIP Round #7】冒泡排序

定义冒泡排序的过程为:

对于一个长为 nn 的序列 a1,…,ana_1,\dots,a_n,进行 n−1n-1 轮“冒泡”操作,每次“冒泡”操作中进行以下操作:

  • 如果 a1>a2a_1>a_2 则交换 a1,a2a_1,a_2。
  • 如果 a2>a3a_2>a_3 则交换 a2,a3a_2,a_3。
  • …\dots
  • 如果 an−1>ana_{n-1}>a_{n} 则交换 an−1,ana_{n-1},a_{n}。

进行一轮“冒泡”操作的伪代码如下:

for i = 1 to n-1:
  if a[i] > a[i + 1]:
    swap(a[i], a[i + 1])

给定一个数组 b1,b2,…,bnb_1,b_2,\dots,b_n。

每次询问 (l,r,k,x,y)(l,r,k,x,y),小 C 截取了 bb 数组的子区间 [l,r][l,r],得到一个新的 aa 数组 [a1,…,ar−l+1]=[bl,…,br][a_1,\dots,a_{r-l+1}] = [b_l,\dots,b_r],并对 aa 数组进行了 kk 次“冒泡”操作。

你需要求出在 kk 次“冒泡”操作后,∑i=xyai\sum_{i=x}^y a_i 的值。

输入格式

第一行一个整数 idid 表示子任务编号。特别的,对于样例输入 11,有 id=0id=0。

第二行两个整数 n,qn,q。

接下来一行 nn 个整数 b1,…,bnb_1,\dots,b_n。

接下来 qq 行每行 55 个整数 l,r,k,x,yl,r,k,x,y。

输出格式

输出 qq 行,每行一个整数表示答案。

0
4 2
1 3 4 2
2 4 1 2 2
1 4 2 3 4
2
7

其余样例

下发文件中共有 88 个样例,分别来自 88 个子任务。

数据范围

对于所有数据:

  • 1≤n≤1061\le n \le 10^6,1≤q≤5×1051\le q\le 5\times 10^5
  • 0≤bi≤1090\le b_i\le 10^9,1≤l<r≤n1\le l < r\le n,1≤k≤r−l1\le k\le r-l,1≤x≤y≤r−l+11\le x\le y\le r-l+1。
子任务编号$n,q$ 范围特殊性质分值
$1$$n \le 10, q \le 5000$无$8$
$2$$n\le 2\times 10^5, q\le 5$无$14$
$3$$n,q\le 2\times 10^5$$x=1,y=r-l+1-k$$10$
$4$$n,q\le 2\times 10^5$$l=1,r=n$$12$
$5$$n,q\le 2\times 10^5$$k\le 10$$14$
$6$$n,q\le 2\times 10^5$$a_i\le 10$$16$
$7$$n,q\le 2\times 10^5$无$16$
$8$$n \le 10^6,q\le 5\times 10^5$无$10$

数据