注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "jumpgame.h"。

题目描述

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「점프 게임」

KOI 公司推出的跳跃游戏是一款通过多次跳跃穿越 $N$ 个踏板的游戏。具体来说，游戏中有 $N$ 个踏板按顺序排列在一条直线上，每个踏板从左到右依次编号为 $0, 1, \ldots, N-1$。游戏开始时，主角站在最左边的 $0$ 号踏板上，初始得分为 $0$。

对于每个 $i$ $(0 \leq i \leq N-1)$，主角可以选择走一步或跳跃。如果选择走一步，主角将移动到 $i+1$ 号踏板，得分不变。如果选择跳跃，主角将移动到 $i+K$ 号踏板，得分增加 $A[i]$。其中 $K$ 是预先设定的常数。游戏在主角到达 $N-1$ 号踏板的右侧时成功结束。也就是说，主角到达编号为 $N, N+1, \ldots$ 的踏板时，游戏结束——这些编号大于等于 $N$ 的踏板实际上不存在，但表示主角已经越过了 $N-1$ 号踏板。游戏的目标是通过合理控制主角的行动，使得分最大化并成功结束游戏。

喜欢网络直播的尚赫偶尔会玩 KOI 公司的跳跃游戏。虽然他自己玩得很开心，但观众们却反应平平。跳跃游戏不受欢迎的原因在于游戏非常困难且枯燥。首先，这款游戏的踏板数量可以多达 $10^{12}$ 个。其次，即使是 KOI 公司的优秀开发者也无法设计出如此多的踏板，因此他们采用了一种相对简单的方法来生成每个踏板。开发者们最初将所有 $A[i]$ 设置为 $0$，然后进行 $Q$ 次操作：对于每个 $j$ $(0 \leq j \leq Q-1)$，他们选择一个区间 $0 \leq L[j] \leq R[j] \leq N-1$，将 $A[L[j]], A[L[j]+1], A[L[j]+2], \ldots, A[R[j]]$ 的值增加 $1$。所有操作完成后的数组 $A$ 就是游戏中每个踏板跳跃时获得的得分。

你是一名制作计算机科学视频的创作者，决定制作一个关于如何以最高得分完成 KOI 公司的跳跃游戏的视频。你认为这个视频会在尚赫的观众中大受欢迎，但你担心游戏规模太大，难以找到高效的算法。克服所有困难，在给定的 5 小时内成为这款游戏的高手吧！

实现细节

你需要实现以下函数：

long long play_game(long long N, int Q, long long K, vector<long long> L, vector<long long> R);

• N：游戏中存在的踏板数量。
• Q：开发者执行的操作次数。
• K：跳跃后到达的下一个踏板的编号。
• L, R：大小为 $Q$ 的整数数组。
• 该函数返回一个整数，表示跳跃游戏结束时可以获得的最高得分。
• 该函数在每个测试点中只会被调用一次。

注意，提交的代码中不应包含任何输入输出操作。

样例 1

考虑 $N=3, Q=5, K=2, L=[0,0,1,1,1], R=[2,2,1,1,1]$ 的情况。

评测程序将调用如下函数：

play_game(3, 5, 2, [0, 0, 1, 1, 1], [2, 2, 1, 1, 1]);

经过 $Q$ 次操作后，得到的数组为 $[2, 5, 2]$。此时可以获得的最高得分是 $5$。获得 $5$ 分的方法之一如下：

• 从 $0$ 号踏板走一步到 $1$ 号踏板。
• 从 $1$ 号踏板跳跃，获得 $5$ 分。
• 到达编号大于等于 $N$ 的踏板，游戏结束。

因此，函数应返回 5。

样例 2

评测程序将调用如下函数：

play_game(250, 8, 50, [0, 40, 49, 50, 100, 149, 199, 75], [200, 140, 49, 150, 190, 199, 199, 249]);

可以获得的最高得分是 $17$。因此，函数应返回 17。

样例 3

评测程序将调用如下函数：

play_game(250, 8, 49, [0, 40, 49, 50, 100, 149, 199, 75], [200, 140, 49, 150, 190, 199, 199, 249]);

可以获得的最高得分是 $19$。因此，函数应返回 19。

样例 4

评测程序将调用如下函数：

play_game(100, 6, 50, [0, 0, 0, 20, 40, 60], [99, 70, 10, 30, 50, 70]);

可以获得的最高得分是 $6$。因此，函数应返回 6。

样例 5

评测程序将调用如下函数：（为了可读性，部分数字之间添加了空格）

play_game(1000000000000, 2, 1, [0, 0], [999999999999, 999999999999]);

可以获得的最高得分是 $2000000000000$。因此，函数应返回 2000000000000。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^{12}$
• $1 \leq Q \leq 2.5\cdot 10^5$
• $1 \leq K \leq N$
• 对于所有 $j$ $(0 \leq j \leq Q-1)$，$0 \leq L[j] \leq R[j] \leq N-1$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$6$	$N \leq 2.5\cdot 10^5$
$2$	$2$	$K=1$
$3$	$13$	$2 K \geq N$
$4$	$15$	$5 K \geq N$
$5$	$16$	$Q \leq 500$
$6$	$7$	$Q \leq 5000$
$7$	$41$	无附加限制

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,Q\,K$
• 第 $2+i$ $(0 \leq i \leq Q-1)$ 行：$L[i]\,R[i]$

示例评测程序按以下格式输出：

• 第 $1$ 行：play_game 返回的值

注意，示例评测程序可能与实际评测程序不同。