[Wc2011]Joy

时间限制:30s      空间限制:259MB

题目描述


输入格式

第一行包含一个正整数 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


题目来源

没有写明来源