← 返回题目列表

AtCoder · abc384_g

G. 绝对总和

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

分数: 575 点

问题陈述

给定整数序列 A=(A_1,A_2,\ldots,A_N) 和 B=(B_1,B_2,\ldots,B_N) 长度 N和整数序列 X=(X_1,X_2,\ldots,X_K) 和 Y=(Y_1,Y_2,\ldots,Y_K) 长度 K.

对于每个 k=1,2,\ldots,K,查找 \displaystyle \sum_{i=1}^{X_k} \sum_{j=1}^{Y_k} |A_i-B_j|.

约束

  • 1\le N\le 10^5
  • 0\le A_i,B_j\le 2\times 10^8
  • 1\le K\le 10^4
  • 1\le X_k,Y_k\le N
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

输出

打印 K 行。 的 i第行 (1\le i\le K) 应包含以下问题的答案 k=i.


样本输入 1

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

示例输出 1

1
4
2
6

对于 k=1,答案是 |A_1-B_1|=1,所以打印 1 在第一行。

对于 k=2,答案是 |A_1-B_1|+|A_1-B_2|=1+3=4,所以打印 4 在第二行。

对于 k=3,答案是 |A_1-B_1|+|A_2-B_1|=1+1=2,所以打印 2 在第三行。

对于 k=4,答案是 |A_1-B_1|+|A_1-B_2|+|A_2-B_1|+|A_2-B_2|=1+3+1+1=6,所以打印 6 在第四行。


示例输入 2

5
1163686 28892 1263085 2347878 520306
1332157 1202905 2437161 1291976 563395
5
5 3
1 5
2 3
1 2
5 5

示例输出 2

13331322
2209746
6366712
207690
20241215