UOJ515 【UR #19】前进四
UOJ 分析 把所有操作离线，按下标从大到小扫描线，并维护一棵以时间为下标的和后缀 $\min$ 有关的线段树。 那么每个操作相当于对某段时间内取 $\min$，一个位置的后缀最小值个数就是它被取 $\min$ 的次数。 用 Segment Tree Beats 维护即可。 具体的，我们只需要维护最大值、严格次大值和最大值被取 $\min$ 的次数，如果最大值 $\leq$ 要取 $\min...
UOJ 分析 把所有操作离线，按下标从大到小扫描线，并维护一棵以时间为下标的和后缀 $\min$ 有关的线段树。 那么每个操作相当于对某段时间内取 $\min$，一个位置的后缀最小值个数就是它被取 $\min$ 的次数。 用 Segment Tree Beats 维护即可。 具体的，我们只需要维护最大值、严格次大值和最大值被取 $\min$ 的次数，如果最大值 $\leq$ 要取 $\min...