#5326. [Jsoi2017]博弈

JSOI 王国的码农JYY 最近沉迷氪金手游无法自拔。由于长期缺少睡眠，他的精神分裂为了善良的JXX 和邪恶的JZZ

，JYY 的人生将何去何从，JXX 和JZZ展开了一场博弈。JYY 的人生共有N个重大事件，按照1,2,…,N编号。如果JX

X 影响了某个事件，JXX 将获得ai的收益，反之如果JZZ 影响了某个事件，JZZ 将获得bi的收益。JXX 和JZZ 面对

这N个事件，将从JXX 开始，轮流选择影响某个事件，这个被选择的事件在以后的回合中将不再能被选择，博弈一

直进行到所有的事件都被某一方影响为止。贪心的JZZ 使用非常简单的策略：每次在剩下的事件中选择bi最大的那

个。bi相同的情况下选择编号i比较小的。善良的JXX 则有更加长远的眼光：他在知道JZZ 的策略情况下，会采用

最优策略最大化他的最终收益减去JZZ 的最终收益的差。现在给出了博弈的初始条件，JYY 想知道最终JXX 的收益

减去JZZ 的收益的差是多少。但使得问题更为困难的是，JXX 会不断修正他对每件事情的估价。JXX 给出了Q 个操

作，每次操作会修改一个事件的ai值，JYY 需要快速计算每次操作后博弈的结果。