P4497 [WC2011] 拼点游戏

小 W 和小 Y 都很喜欢玩一种“拼点游戏”。游戏中两个人分别通过某种操作产生一个数作为自己的“点数”，点数大的一方获胜。“拼点游戏”的规则如下： 1. 游戏开始时，给定一个包含 $n$ 个元素的正整数序列 $U=(u_1,u_2,\cdots,u_n)$。 2. 定义 $U$ 的一个下标序列 $I=(i_1,i_2,\cdots,i_m)$ 是满足 $1\leq i_1

无

无

【评分标准】 一个测试点包含多组测试数据，对于该测试点： 如果所有的 $D_{max}$ 均正确但某个 $X$ 不正确，则可以得到3分； 如果所有的 $X$ 均正确但某个 $D_{max}$ 不正确，则可以得到7分； 如果所有回答均正确，则可以得到 10 分。 【样例说明】 输入数据包含两组测试数据。 在第一组测试数据中：第一次“拼点游戏”时，最优下标序列为 $(1,2,4,5)$，小 Y 只需要进行一次修改操作：选择 $k=1$，以及非负整数 $z_1=1,z_2=0$。这样经过修改操作之后下标序列将变为 $(1,3,4,5)$，小 Y 获胜。 第三次“拼点游戏”时，序列 $U$ 为 $(9,8,6,5,3)$，小 W 所选择的最优下标序列为空序列，所产生的点数为 $0$。在这种情况下，小 Y 无法进行任何修改操作（也无需进行任何修改操作），此时小 Y 已经直接获胜。 【数据规模】 对于 10% 的数据满足 $n,q\leq 13$； 对于 30% 的数据满足 $n,q\leq 1000$； 对于另外 20% 的数据满足 $T=1$ 且 $n\leq 40000$； 对于 100% 的数据满足 $T\leq 3$ 且 $n,q\leq 10^5$，同时初始序列 $U$ 满足 $0