#384. E - 货物集中作业

E - 货物集中作业

E - 货物集中作业

题目描述

有 NN 座仓库从西向东排成一条直线,从西往东依次编号为 1,2,…,N1,2,\ldots,N,相邻两座仓库之间的距离为 11。

初始时,仓库 ii 中有 AiA_i 件货物。

高桥和青木依次进行 QQ 次货物集中作业。第 jj 次作业指定一个闭区间 [Lj,Rj][L_j,R_j]:高桥的卡车停在仓库 LjL_j,青木的卡车停在仓库 RjR_j。

在这次作业中,作业开始时位于区间 [Lj,Rj][L_j,R_j] 内每座仓库的全部货物,都要被搬运到两个端点仓库中距离它更近的那个。如果到两个端点的距离相同,就搬运到左端点 LjL_j。

搬运一件货物、距离为 dd 的花费是 dd。

货物会真实地移动到目标仓库,因此后续操作基于更新后的货物分布。当前指定区间外的货物不会移动。

对于每次作业,依次输出该次作业的总搬运花费。

输入格式

第一行输入两个整数 N,QN,Q。

第二行输入 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来 QQ 行,每行输入两个整数 Lj,RjL_j,R_j。

输出格式

输出 QQ 行,第 jj 行输出第 jj 次作业产生的总搬运花费。

注意:花费可能超过 32 位整数范围,需要使用 64 位整数。

数据范围

  • 2≤N≤2×1052\le N\le2\times10^5
  • 1≤Q≤1051\le Q\le10^5
  • 0≤Ai≤1060\le A_i\le10^6
  • 1≤Lj<Rj≤N1\le L_j<R_j\le N
  • 所有输入均为整数。

样例输入 1

5 3
2 0 3 1 4
1 3
2 5
1 5

样例输出 1

0
4
3

样例输入 2

5 4
0 5 2 5 0
1 5
2 4
1 2
4 5

样例输出 2

14
0
0
0

样例输入 3

12 8
10 0 5 3 8 2 0 7 1 4 6 9
1 6
4 12
2 9
5 6
1 12
7 11
3 10
6 8

样例输出 3

24
71
40
0
20
0
0
0

样例输入 4

30 20
5 0 12 7 100 3 8 15 0 21 4 9 30 2 17 6 11 0 25 14 1 18 7 33 0 10 5 28 13 19
1 30
5 20
10 25
2 3
14 18
7 29
1 15
16 30
8 9
12 27
3 22
20 21
4 30
1 2
9 17
6 24
11 13
15 28
2 19
23 30

样例输出 4

2731
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

样例输入 5

2 1
0 1000000
1 2

样例输出 5

0