#PQJ1827x9610. QOJ 1827_9610
QOJ 1827_9610
标题: 游戏 - Problem - QOJ.ac
#9610. 游戏
The problem was used in the following contests:
小 A 和小 B 喜欢玩游戏。
他们在数轴上玩游戏,数轴上的一些位置放着物品,最初他们有一个参数 k,保证 k=0/1。
接下来小 A 会选定一个位置 x,那么小 B 的位置就为 x+k,两个人会轮流取走物品,由小 A 先手。
对于当前操作的玩家,他会取走当前剩余物品中离自己的位置距离最近的一个物品,如果有两个物品距离相同,则他会取走位置更小的那个物品。
位置 a 和 b 的距离定义为 |a−b|。
最后,在所有物品都被取走后,小 A 想知道,他手上的物品位置的总和是多少。
但是,由于他们非常的闲,他们会进行 q 次游戏,每次游戏结束后所有物品都会恢复原位置,对于每次游戏小 A 都想知道对于当前的位置 x,小 B 的位置 x+k,游戏完后小 A 手上的物品位置的总和。
输入格式
第一行三个数 n,q,k,表示数轴上存在 n 个区间的物品,小 A 和小 B 的游戏次数和初始选定的参数。
接下来 n 行,每行两个数 li,ri 表示在区间 [li,ri] 中的每个位置都有一个物品。
接下来 q 行,每行一个数 x,表示此轮游戏小 A 的参数为 x,小 B 的参数为 x+k。
输出格式
设 ansi 表示第 i 次询问的答案,那么输出一个整数表示 ⊕i=1qi×ansi。
样例输入 1
4 2 1
4 5
7 8
10 11
13 13
6
8
样例输出 1
16
样例 1 解释
对于 x=8 的询问。
小 A 在结束时手上的物品的位置为 8,7,5,4。
小 B 在结束时手上的物品的位置为 10,11,13。
因此结束时小 A 手上的物品位置的总和为 8+7+5+4=24。
对于 x=6 的询问,答案为 32。
样例输入 2
7 6 0
2 2
4 5
7 8
9 9
13 13
15 15
18 20
19
15
18
17
11
5
样例输出 2
468
样例 3,4
见下发文件,分别满足子任务 2,4 的性质。
数据范围
对于所有数据,保证:1≤n≤5000,1≤q≤2×106,1≤x≤5×106,1≤li≤ri≤5×106,k=0/1,∀i∈[1,n−1],ri<li+1。
subtask 1(15 分):q≤2000;
subtask 2(25 分):k=0;
subtask 3(20 分):k=1,li=ri;
subtask 4(40 分):无。