"Zhouchuan slaves to the history.
Even after the calamity, Zhouchuan is still against the only rule that can guarantee the safety of Zhouchuan's people.
Zhouchuan solely, are responsible for this."
题目描述
给定函数：
function cocktailSort(A,N,k):
for cnt = 1 to k:
for i = 1 to N-1:
if A[i+1] < A[i]:
swap A[i], A[i+1]
for i = N-1 downto 1:
if A[i+1] < A[i]:
swap A[i], A[i+1]给定一长度为 n 的排列 A 和 q 次查询，每次查询给定 k,l,r，表示求运行 cocktailSort(A,n,k) 之后 r∑i=lAi 的值。
每次询问相互独立。
输入格式
第一行两个整数 n,q。 第二行 n 个整数表示排列 A。 接下来 q 行，每行三个整数，表示一次询问的 k,l,r。
输出格式
输出 q 行，每行一个整数表示答案。
样例输入 #1
3 1
2 1 3
2 1 2样例输出 #1
3样例 1 解释
运行 cocktailSort([2,1,3],3,1) 之后的结果是 [1,2,3]，前两项求和是 3。
数据范围
对于所有数据，满足 1≤n,q≤5×105，1≤k≤109，1≤l≤r≤n。
| 测试点编号 | n | q | k | 特殊性质 | |
|---|---|---|---|---|---|
| 1,2 | ≤1000 | ≤100 | ≤100 | ||
| 3,4 | ≤1000 | ≤105 | ≤109 | ||
| 5,6,7 | ≤105 | ≤10 | ≤109 | ||
| 8,9,10 | ≤105 | ≤105 | ≤109 | A | |
| 11,12,13 | ≤105 | ≤105 | ≤109 | B | |
| 14,15,16 | ≤105 | ≤105 | ≤109 | C | |
| 17,18 | ≤105 | ≤105 | ≤109 | D | |
| 19 | ≤105 | ≤105 | =109 | ||
| 20,21,22 | ≤105 | ≤105 | ≤109 | ||
| 23,24,25 | ≤5×105 | ≤5×105 | ≤109 |
其中特殊性质分别为：
- A：k 最多 10 种取值；
- B：r≤10；
- C：l=r；
- D：l 最多 10 种取值，r 最多 10 种取值。