差后专题

2023NOIP A层联测22-差后队列

定义差后队列为一个数据结构,支持两种操作: pop 随机删除一个不是最大值的的数。如果只有一个数则删除该数。push 插入一个数(正常插入)。 给定操作序列,求每次删的数的期望,以及每个数期望被删的时间(如果到最后也没被删则删除时间为 0 0 0)。 n ≤ 1 0 6 n\le10^6 n≤106 容易发现,一个数如果不是最大值,都是一样的。 对于一个数,如果它是当前的最大值,