| 题目名称 | 1782. [国家集训队2012]世博会 |
|---|---|
| 输入输出 | nt2012_lhx_dis.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-31加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：34， 提交：82， 通过率：41.46% | ||||
 Hzoi_Hugh |
100 | 2.495 s | 2.71 MiB | C++ |
|
Hzoi_Hugh |
100 | 2.571 s | 2.11 MiB | C++ |
 Hallmeow |
100 | 2.729 s | 195.27 MiB | C++ |
 Hzoi_moyi |
100 | 2.813 s | 80.43 MiB | C++ |
 Narcissus |
100 | 2.871 s | 4.89 MiB | C++ |
 小一米 |
100 | 2.991 s | 75.09 MiB | C++ |
 天亮说晚安· |
100 | 3.067 s | 48.38 MiB | C++ |
 Nawox |
100 | 3.168 s | 82.72 MiB | C++ |
 Cooook |
100 | 3.650 s | 126.94 MiB | C++ |
|
小一米 |
100 | 3.951 s | 127.73 MiB | C++ |
| 关于 世博会 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
max(|x1-x2|,|y1-y2|)
=0.5*(|(x1-x2)+(y1-y2)|+|(x1-x2)-(y1-y2)|) =|(x1+y1)/2-(x2+y2)/2|+|(x1-y1)/2-(x2-y2)/2|  _Itachi
2017-02-28 14:33
5楼
| ||||
|
可持久化01Trie大法好，非递归追求卓越！
| ||||
|
| ||||
|
数据没有诚意啊。 打错两个关键的变量名竟然都能得95分。
| ||||
|
论如何强行出一道主席树……
 cstdio
2014-11-02 20:10
1楼
| ||||
天一阁
rpCardinal
世博会(刘洪轩)
时间限制：2.0s 内存限制：256.0MB
【题意描述】
感谢HQ提供题目描述
四年一度的世博会又要举办了，Q国很荣幸成为了这次世博会的主办方。Q国主席QQ从全国各地收集了N件物品排成一排，作为Q国馆的展出物。
对于相邻摆放的一些物品，如果过于相似会让人觉得无聊，如果差别过大又会让人觉得突兀。为了让人们对这次世博会的展出满意，QQ需要知道一些相邻物品的“差异度”。为了方便表示，QQ给每个物品都定义了两个属性值A、B，两件物品之间的“绝对差异值”定义为它们对应属性的差的绝对值较大的一个。对于一些物品的“差异度”，类似求方差的方法，QQ总会首先设想一个理想的“平均物品”，它的两个属性可以为任意实数，且它与这些物品中的每个物品的“绝对差异值”之和最小。而这些物品的“差异度”就定义为这个最小的和。QQ每次会询问：从第Li个到第Ri个物品的“差异度”是多少。现在，这个任务交给了神犇你。
四年一度的世博会又要举办了，Q国很荣幸成为了这次世博会的主办方。Q国主席QQ从全国各地收集了N件物品排成一排，作为Q国馆的展出物。
对于相邻摆放的一些物品，如果过于相似会让人觉得无聊，如果差别过大又会让人觉得突兀。为了让人们对这次世博会的展出满意，QQ需要知道一些相邻物品的“差异度”。为了方便表示，QQ给每个物品都定义了两个属性值A、B，两件物品之间的“绝对差异值”定义为它们对应属性的差的绝对值较大的一个。对于一些物品的“差异度”，类似求方差的方法，QQ总会首先设想一个理想的“平均物品”，它的两个属性可以为任意实数，且它与这些物品中的每个物品的“绝对差异值”之和最小。而这些物品的“差异度”就定义为这个最小的和。QQ每次会询问：从第Li个到第Ri个物品的“差异度”是多少。现在，这个任务交给了神犇你。
【输入格式】
第一行两个整数N和Q，表示物品数和QQ的询问数。
第二行N个整数A1到An，表示每个物品的A属性。
第三行N个整数B1到Bn，表示每个物品的B属性。
之后Q行每行两个整数Li Ri，表示QQ的询问。
第二行N个整数A1到An，表示每个物品的A属性。
第三行N个整数B1到Bn，表示每个物品的B属性。
之后Q行每行两个整数Li Ri，表示QQ的询问。
【输出格式】
共Q行，每行输出一个数，表示该次询问的物品的差异度，结果保留到小数点后两位。
【样例输入】
4 2
1 6 -3 2
2 7 -1 3
1 4
2 3
1 6 -3 2
2 7 -1 3
1 4
2 3
【样例输出】
10.00
9.00
9.00
【样例说明】
对于第一个询问，平均物品的两个属性可以是1和2
差异度为max(0,0)+max(5,5)+max(4,3)+max(1,1)=10
对于第二个询问，平均物品的两个属性可以是6和7
差异度为max(0,0)+max(9,8)=9
差异度为max(0,0)+max(5,5)+max(4,3)+max(1,1)=10
对于第二个询问，平均物品的两个属性可以是6和7
差异度为max(0,0)+max(9,8)=9
【数据规模和约定】
对于10%的数据，1<=N<=100, Q=1且L1=1, R1=N, |Ai|,|Bi|<=100
对于20%的数据，1<=N<=1000, 1<=Q<=10, |Ai|,|Bi|<=1000000
对于40%的数据，1<=N<=10000, 1<=Q<=500, |Ai|,|Bi|<=1000000
对于60%的数据，1<=Q<=500
对于100%的数据，1<=N<=100000, 1<=Q<=100000, |Ai|,|Bi|<=1000000000
对于100%的数据，1<=Li<=Ri<=N
对于20%的数据，1<=N<=1000, 1<=Q<=10, |Ai|,|Bi|<=1000000
对于40%的数据，1<=N<=10000, 1<=Q<=500, |Ai|,|Bi|<=1000000
对于60%的数据，1<=Q<=500
对于100%的数据，1<=N<=100000, 1<=Q<=100000, |Ai|,|Bi|<=1000000000
对于100%的数据，1<=Li<=Ri<=N