题目详情题解（0）讨论（0）提交记录（0）

AT_abc384_g.[ABC384G] Abs Sum

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 NN 的整数序列 A,BA,B 和长度为 KK 的正整数序列 X,YX,Y，对于 k=1,2,3,...,Kk=1,2,3,...,K，求 ∑i=1Xk∑j=1Yk∣Ai−Bj∣\sum_{i = 1}^{X_k} \sum_{j = 1}^{Y_k} |A_i-B_j|。

输入格式

第一行输入一个整数 NN。
第二行输入 NN 个整数 A1,A2,A3,...,ANA_1,A_2,A_3,...,A_N。
第三行输入 NN 个整数 B1,B2,B3,...,BNB_1,B_2,B_3,...,B_N。
第四行输入一个整数 KK。
接下来共 KK 行，每行两个整数，第 ii 行输入的数为 Xi,YiX_i,Y_i。

输出格式

输出共 KK 行，每行一个整数，第 ii 行表示当 k=ik=i 时的结果。

输入输出样例

  • 输入#1

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

    输出#1

    1
4
2
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

说明/提示

样例解释

测试数据1

当 k=1k=1 时，答案为 ∣A1−B1∣=1|A_1-B_1|=1，因此第 11 行输出一个整数 11。
当 k=2k=2 时，答案为 ∣A1−B1∣+∣A1−B2∣=1+3=4|A_1-B_1|+|A_1-B_2|=1+3=4，因此第 22 行输出一个整数 44。
当 k=3k=3 时，答案为 ∣A1−B1∣+∣A2−B1∣=1+1=2|A_1-B_1|+|A_2-B_1|=1+1=2，因此第 33 行输出一个整数 22。
当 k=4k=4 时，答案为 ∣A1−B1∣+∣A1−B2∣+∣A2−B1∣+∣A2−B2∣=1+3+1+1=6|A_1-B_1|+|A_1-B_2|+|A_2-B_1|+|A_2-B_2|=1+3+1+1=6，因此第 44 行输出一个整数 66。

数据范围

  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤Ai,Bj≤2×1080 \leq A_i,B_j \leq 2 \times 10^8
  • 1≤K≤1041 \leq K \leq 10^4
  • 1≤Xk,Yk≤N1 \leq X_k,Y_k \leq N

输入解题思路，AI测评打分。不知道怎么写?

首页