#PQJ1827x9610. QOJ 1827_9610

    ID: 2722 传统题 3500ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测线段树分块

QOJ 1827_9610

标题: 游戏 - Problem - QOJ.ac

#9610. 游戏

Statistics

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 分):无。