充分利用序列的栈性质

思路

核心

缓存历史记录备查

注意到：只要栈底$n$个数不被影响，那么无论过程如何，当栈深回到$n$，众数不变。

动态规划性质

入栈一个元素x时，只有x的出现次数变化（且是增加），众数要么不变，要么变成x。常数复杂度。

出栈一个元素时，众数回退到历史结果。常数复杂度。

粗略设计

• 栈V[]存放序列；
• 栈M[]存放历史众数，满足M[i]等于V[：i+1]的众数；
• 散列表C实时记录序列中各个数的出现次数。

为了压缩，不一个个保存数，而是将序列中连续相同数的极长子序列记作{value, count}结构入栈。入栈和出栈的众数更新算法相应有所变化。

代码

class Q:
    class Node:
        def __init__(self, x: int, k: int):
            self.x = x
            self.k = k

    def __init__(self):
        self.values = []
        self.modes = []
        self.counts = {}

    def push(self, k: int, x: int):
        assert len(self.values) == len(self.modes)
        if len(self.values) == 0:
            self.counts[x] = k
            self.values.append(Q.Node(x, k))
            self.modes.append(x)
            return

        tail, mode = self.values[-1], self.modes[-1]
        if tail.x != x:
            self.counts.setdefault(x, 0)  # works iff. x not in self.counts.keys()
            self.values.append(Q.Node(x, k))
            self.modes.append(mode)
        else:  # 合并相邻相同元素
            tail.k += k
        self.counts[x] += k
        if mode != x and (cx:=self.counts[x]) >= (cm:=self.counts[mode]):  # 更新众数
            if cx > cm or x < mode:
                self.modes[-1] = x
    
    def pop(self, k: int):
        assert len(self.values) == len(self.modes)
        while k > 0:  # 按块删除
            if len(self.values) == 0:
                return
            tail = self.values[-1]
            if k >= tail.k:  # 栈顶全删
                kd = tail.k
                self.counts[tail.x] -= kd
                self.values.pop()
                self.modes.pop()
            else:  # 栈顶更新
                kd = k
                self.counts[tail.x] -= kd
                tail.k -= kd

                if (mode:=self.modes[-1]) == tail.x:  # 被删数之前是众数，现在出现次数减小了
                    if len(self.modes) >= 2:
                        y = self.modes[-2]  # 新众数候选
                        cy = self.counts[y]
                        cm = self.counts[mode]
                        if cy > cm or (cy == cm and y < mode):
                            self.modes[-1] = y
            k -= kd  # 循环控制
    
    def most(self) -> int:
        return self.modes[-1] if len(self.modes) > 0 else -1