← 返回题目列表

AtCoder · past202212_n

N. 顺序和功能

中文机器翻译题面 查看原题

问题陈述

对于整数序列 X = (X_1, X_2, \dots, X_k),让我们定义一个函数 f(X) 如下:

  • 让 Y = (Y_1, Y_2, \dots, Y_k) 为排序得到的序列 X 按升序排列。
  • 然后, \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2.

我们有一个整数序列 A = (A_1, A_2, \dots, A_N)。 给定 Q 查询如下格式,按顺序处理。

  • 给定整数 l 和 r,查找 f(B),其中 B = (A_l, A_{l + 1}, \dots, A_r).

约束

  • 输入中的所有值都是整数。
  • 1≤N≤2\times10^4
  • 1≤A_i≤10^9
  • 1≤Q≤10^5
  • 对于每个查询, 1≤l≤r≤N.

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N
Q
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q

在这里, \text{Query}_i 表示 i第一个查询。 每个查询均按以下格式给出:

l r

输出

打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

3
3 1 4
4
1 1
1 2
2 3
1 3

示例输出 1

0
4
9
5

我们有 A = (3, 1, 4).

  • 在 1-st 查询, f(B) = 0,因为排序 B = (3) 按收益率升序排列 (3).
  • 在 2-nd 查询, f(B) = 4,因为排序 B = (3, 1) 按收益率升序排列 (1, 3).
  • 在 3-rd 查询, f(B) = 9,因为排序 B = (1, 4) 按收益率升序排列 (1, 4).
  • 在 4第一个查询, f(B) = 5,因为排序 B = (3, 1, 4) 按收益率升序排列 (1, 3, 4).

示例输入 2

10
19 70 14 11 85 75 72 35 14 50
10
1 1
3 8
5 7
1 3
5 8
5 5
2 10
2 5
1 5
2 9

示例输出 2

0
1928
109
2626
1478
0
1188
3370
2860
1788