小塔和小美在玩一个卡牌游戏,初始时桌面上有n种卡牌,每种卡牌有ai张,这些牌都是背面朝上的。玩家操作时会先翻一张牌,然后再翻一张牌,若两张牌的类型相同,则玩家获胜,否则,重新将两张票翻回背面朝上,两个玩家轮流操作。
小塔和小妹总共会玩q+1轮游戏。第1轮的卡牌数量为初始数量,后续每一轮会在上一轮游戏的基础上,增加或减少一些卡牌,然后将所有卡牌翻至背面朝上并重新打乱。
增加卡牌的操作为:+l r x 表示第l种牌到第r种牌各增加x张。
增加卡牌的操作为:−l r x 表示第l种牌到第r种牌各减少x张。
每一轮都是由小塔先手,小塔想让小妹获胜,小塔想知道他至少需要偷看多少张牌才能保证小妹一定能获得胜利?若无法保证小美一定获得胜利,则输出−1
第一行输入2个正整数n,q(1≤n,q≤105),表示卡牌种类和游戏轮数。
第2行输入n个整数ai(0≤ai≤109)表示数组。
接下来q行,每行先输入1个字符c(c∈{′−′,′+′}),再输入3个数字l,x(1≤l≤r≤n),x(1≤x≤109),表示操作。
数据保证,任意一轮开始前,每种卡牌的数量都为非负整数,且每种卡牌数量之和不小于2
输出q+1行,每行输出一个整数表示答案。
输入
2 1
1 1
+ 2 2 1
输出
-1
1
说明
第1轮,很显然,小塔和小美永远都赢不了。
第2轮,小塔可以偷看1张牌,若看到的是第1种牌,则翻开这张牌和任意一张其他牌;若看到的是第2种牌,则翻开另外两张牌。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.