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

输入文件 joy.in 的第一行包含一个正整数 $T$，表示测试数据的组数。接下来为 $T$ 组数据。 每一组数据的第一行包含两个整数 $n$ 和 $q$，分别表示 $U$ 中的元素个数和事件个数。 接下来的一行，包含 $n$个 用一个空格隔开的正整数，第 $i$ 个整数为初始的序列中第 $i$ 个元素 $u_i$。 接下来 $q$ 行，每行代表一个事件（按事件发生顺序输入）。每行的第一个数非 $0$ 即 $1$，表示这个事件的类型。 若为 $0$ ：在 $0$ 之后还有三个整数 $l$，$r$ 和 $c$（这四个数之间均有一个空格）表示小 W 将 $u_l,u_{l+1},\cdots,u_r$ 增加 $c$； 若为 $1$：表示两人进行了一次“拼点游戏”，你需要输出相应的结果。 输入数据保证序列 $U$ 中的所有元素总是正整数。

输出文件为joy.out。对于每一组测试数据，依次对每一次“拼点游戏”输出一行包含两个由一个空格隔开的整数 $D_{max}$ 和 $X$，其中 $D_{max}$ 为对于当前序列 $U$，小 W 所能选出的最优下标序列所对应的点数； $X$ 表示小 Y 最少需要进行几次修改操作才能获胜。如果小 Y 不论多少次操作都无法获胜，则输出```-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