#1112. 2116. [Wc2011]Joy

2116. [Wc2011]Joy

#2116. [Wc2011]Joy

题目描述

image

输入格式

第一行包含一个正整数 T,表示测试数据的组数。接下来为 T组数据。 每一组数据的第一行包含两个整数 n 和 q, 分别表示 U中的元素个数和事件个数。 接下来的一行,包含n 个用一个空格隔开的正整数,第 i 个整数为初始的序列中第 i 个元素 ui。 接下来 q 行,每行代表一个事件(按事件发生顺序输入) 。每行的第一个数非 0 即 1,表示这个事件的类型。 若为 0 :在 0 之后还有三个整数 l,r 和 c(这四个数之间均有一个空格) ,表示小 W将Ul,Ul+1,....Ur௥增加 c; 若为 1 :表示两人进行了一次"拼点游戏" ,你需要输出相应的结果。 输入数据保证序列 U中的所有元素总是正整数。

输出格式

对于每一组测试数据,依次对每一次"拼点游戏"输出一行包含两个由一个空格隔开的整数 Dmax 和 X,其中 Dmax 为对于当前序列 U,小 W所能选出的最优下标序列所对应的点数; X 表示小 Y 最少需要进行几次修改操作才能获胜。如果小 Y 不论多少次操作都无法获胜,则输出-1。 数据保证最优下标序列总是唯一的。

样例

样例输入

2   

5 9   

9 10 7 6 8   

1   

0 4 5 2   

0 3 5 4   

1   

0 2 5 -2   

0 3 5 -3   

0 4 5 -2   

0 5 5 -4   

1   

4 3   

2 4 3 5   

1   

0 3 3 3   

1 

样例输出

3 1   

5 -1   

0 0   

4 -1   

4 -1 

数据范围与提示

输入数据包含两组测试数据。 在第一组测试数据中: 第一次"拼点游戏"时,最优下标序列为(1,2,4,5),小 Y只需要进行一次修改操作:选择 k=1,以及非负整数 z1=1,z2=0。这样经过修改操作之后下标序列将变为(1,3,4,5),小 Y获胜。 第三次"拼点游戏"时,序列 U为(9,8,6,5,3),小 W所选择的最优下标序列为空序列,所产生的点数为 0。在这种情况下,小Y无法进行任何修改操作(也无需进行任何修改操作) ,此时小 Y已经直接获胜。 对于10%的数据满足 n,q ≤ 13; 对于30%的数据满足 n,q ≤ 1000; 对于另外20%的数据满足 T=1 且 n ≤ 40000; 对于100%的数据满足 T ≤ 3 且 n, q ≤ 10^5 同时初始序列 U满足 0