11月24日 模拟赛 题解

(A)

模拟。 时间复杂度 ： (O(N))

(B)

考虑两个数怎样排更优。 时间复杂度 : (O(NlogN))

(C)

一个数在经过一次操作后贡献就是 (0) 了。

所以维护最大值的线段树 ， 每次在上面找未被删除的 ， 贡献清零后权值变为 (-infty)。

每个数最多删一次 ， 时间复杂度 (O(NlogN))

(D)

假设初始区间 ([l , r]) 对应坐标轴原点。

那么删前面的相当于从 ((x , y)) 走到 ((x + 1 , y)) , 删后面的相当于走到 ((x ， y + 1))。

注意到若 ((x + 1 , y + 1)) 必败 ， 那么 ((x , y)) 必败 ， 若 ((x + 1 , y + 1)) 和 ((x + 2 , y + 2)) 必胜 ， 则 ((x , y)) 必胜。

因此询问等价于询问右上最大点的状态。

时间复杂度 : (O(QlogN))