【NOIP Round #5】青鱼和游戏 - Problem

本题是 IOI Style 的交互题。

由于 PJudge 缺头，鱼王青鱼和他的得力助手缺头鱼今天在玩几个造题 AI。

题目描述

鱼王青鱼使用 GameGPT 生成了一个博弈游戏。

现在青鱼和缺头鱼玩这么一个游戏 : 有若干对石子堆，一开始第 $i$ 对中两堆分别包含 $a_i$ 个石子。青鱼每轮可以选择一堆石子，从中拿走任意正整数个；缺头鱼每轮可以选择一堆石子，从中拿任意正整数个石子放到和它配对的堆里去。青鱼先手。所有石子堆都为空时游戏结束。青鱼希望游戏尽可能短，缺头鱼希望游戏尽可能长，求如果两鱼都按最优策略行动，他们一共会进行多少次操作。

青鱼又把这个游戏喂给了 OIGPT，所以你还需要支持对 $a$ 单点修改，每次查询 $a$ 的一个区间中上述问题的答案。

设 $n$ 为序列长度， $q$ 为操作数，有 $n,q\leq 5\times 10^6$ 。

交互格式

你不需要，也不应该实现主函数。你需要使用 #include"game.h"，并实现以下三个函数 :

void build(std::vector<long long> a,bool flag) : 这个函数将会在每组测试开始时调用，参数为题中的序列 $a$ （下标从 $1$ 开始，a[0] 为 $0$ ）以及标志是否有修改操作的 $flag$ ， $flag=0$ 表示没有修改操作，否则表示有；你可以用 a.size()-1 获取 $n$ 。你此时不知道 $q$ 。
void modify(int p,long long x) : 表示把 $a_p$ 修改为 $x$ 。
int query(int l,int r) : 表示查询区间 $[l,r]$ 的答案。

保证每次运行中 build 调用恰好一次，且 modify 和 query 的所有调用在 build 之后。

为了方便选手调试，下发了一个样例交互库。你可以把 game.h implementer.cpp 和你的代码（假设名为 code.cpp）放到同一文件夹下，并使用 g++ code.cpp implementer.cpp -o code -std=c++14 -O2 进行编译（对于 Windows 选手，使用 g++ code.cpp implementer.cpp -o code.exe -std=c++14 -O2 -Wl,--stack=2147483647）。

样例交互库输入格式 :

第一行三个数 $n,q,flag,t$ ，其中 $q$ 为操作次数， $t$ 为一个关于输出格式的参数。

接下来一行 $n$ 个数，表示初始序列。

接下来 $q$ 行，每行三个数 $o,x,y$ ， $o=1$ 表示查询区间 $[x,y]$ 的答案， $o=2$ 表示把 $a_x$ 修改为 $y$ 。

样例交互库输出格式 :

如果 $t=1$ 则对于每次查询，一行一个数表示答案；如果 $t=0$ 则输出所有查询答案的字符串哈希值。你可以阅读 implementer.cpp 了解哈希的具体方式。

保证实际测试中使用的交互库占用时间不超过对应测试点时间限制的 $\frac{1}{10}$ ，空间不超过对应测试点空间限制的 $\frac{1}{3}$ 。

输入输出样例

样例1输入

4 1 0 1
3 3 3 3
1 1 4

样例1输出

样例1解释

这是游戏的一种可能的过程，其中每一步都是最优的。数字表示每一堆的石子个数，每两堆是一对。

3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 0
3 3 3 3 3 3 1 2
3 3 3 3 3 3 1 0
3 3 3 3 3 3 0 1
3 3 3 3 3 3 0 0
3 3 3 3 2 4 0 0
3 3 3 3 2 0 0 0
3 3 3 3 1 1 0 0
3 3 3 0 1 1 0 0
3 3 1 2 1 1 0 0
3 3 1 0 1 1 0 0
3 3 0 1 1 1 0 0
3 3 0 0 1 1 0 0
2 4 0 0 1 1 0 0
2 0 0 0 1 1 0 0
1 1 0 0 1 1 0 0
1 0 0 0 1 1 0 0
0 1 0 0 1 1 0 0
0 0 0 0 1 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0

样例2输入

8 10 0 1
1 3 1 4 1 3 1 4 
1 5 7
1 2 3
1 2 5
1 2 3
1 2 4
1 2 8
1 4 7
1 5 6
1 3 8
1 2 6

样例2输出

样例3~5

请见下发文件。

数据范围及约束

本题共有 $20$ 个测试点，各测试点等分。

如无特殊说明，空间限制为 128mb，时间限制为 1s。

对于第 $1$ 个测试点，没有查询。

对于前 $3$ 个测试点， $n\leq 8,a_i\leq 4,q\leq 100$ 。

对于第 $4$ 个测试点，对于某个 $k$ 和所有 $i$ 有 $a_i=2^k$ 。

对于第 $5$ 个测试点，对于某个 $k$ 和所有 $i$ 有 $a_i=2^k-1$ 。

对于第 $6$ 个测试点， $n,q\leq 1000$ 。

对于前 $8$ 个测试点，没有修改。

对于第 $9,10,11$ 个测试点，空间限制为 1024mb，时间限制为 3s。

对于第 $12,13,14$ 个测试点，时间限制为 3s。

对于前 $16$ 个测试点， $n,q\leq 2\times 10^6$ 。

对于第 $17,18,19,20$ 个测试点， $n,q\leq 5\times 10^6$ ，空间限制为 512mb，时间限制为 3s。

对于所有测试点， $n,q\leq 5\times 10^6,n\geq 1,0< a_i< 2^{40}$ 。

请注意空间限制。

Public Judge

pjudge

PNR #5

D. 【NOIP Round #5】青鱼和游戏