分数: 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