PKUWC2020乱做
D2T1 火山哥与打铁传说
题意：你有 (n) 条鱼，每条为毒鱼或小鱼，敌方有神盾鱼和大鱼。任意鱼和神盾鱼对战后都会将神盾鱼变成大鱼，只有毒鱼和大鱼对战能杀死大鱼，小鱼对战大鱼无影响。
(q) 次询问 ((k,x)) 表示，在对方开始时已经有 (x) 条大鱼的情况下，你用 编号 (1) 到 (k) 的鱼依次与对方对战，假设有 (y) 条神盾鱼，最大化 (y) 使得能全部打完
(n,q leq 4*10^5)
题解：考虑二分答案
设有 (mid) 条神盾鱼，记 (pos_i) 表示第 (i) 条毒鱼的位置，(s) 为编号为 (1) 到 (k) 中的毒鱼个数
显然用最前 (x) 条毒鱼给大鱼，最后 (mid) 条毒鱼给神盾鱼完成 致命一击 最优，然后就可以把其他的毒鱼当成小鱼
那么要保证最后 (mid) 条毒鱼上场的时候，有神盾鱼让他完成致命一击
考虑在原序列上，毒鱼为 -1，小鱼为 +1
即要保证 (forall i in [pos_{s-mid+1},pos_s] sum_i geq -(pos_{s-mid+1}-1-x))
用随便什么东西判断即可，注意常数