在一个神奇的世界里,魔法元素是非常重要的,它们有着巨大的能量。魔法师塔子哥也是这个世界的一名著名的魔法师,他掌握了许多神奇的魔法。但他总是想知道,使用他所拥有的魔法元素,是否有足够的能量施展出一种强大的魔法。
我们通过前缀积来求解。我们val表示前缀积,ne和po分别表示所有前缀积中负数和正数的个数,ans1和ans2记录答案。假如我们枚举到i,此时val大于0,那么表示[1,i]的数组乘积为正,此时由于我们知道po和ne,由于正数除正数是正数,正数除负数是负数可以知道,有几个po就可以有几个[k,i]数组乘积为正(k是前缀积为正时对应的下标(K<=i)),反之ne可以知[k,i]乘积为负,除此以外,正数的个数还要加1,原因是[1,i]也是正数。负数也类似的讨论