[雅礼1706 Day 7] 回转寿司

n 个数的序列 x, 依次进行 q 个操作: 给定 s, t, p

for (int i = s; i <= t; ++i)
    if (x[i] > p)
        swap(x[i], p);

对于每次操作, 输出 p 最终变成了多少 (并执行修改). (1 ≤ n ≤ 4*10^5, 1 ≤ q ≤ 25000, 1 ≤ xi, p ≤ 10^9) 先考虑 s = 1, t = n.

很容易看出, p 最终变成 max { p, x[i] }, 和 x 中元素的顺序无关. 当 p < max { x[i] }, x 中的最大元素被替换成 p; 否则, 没有改动. 这时, 我们用一个大根堆就可以搞定了.

q ≤ 25000, 提示我们考虑一下根号算法.

对序列进行分块. 每块一个大根堆. 零碎的块暴力. 对于整块, 这样能较快速地得到答案, 但是怎么修改呢? 对于一个块 x[1],x[2],...,x[m], 先打上标记, 假设它们是 p[1],p[2],...,p[k]. 我们执行的实际上是以下过程:

for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= k; ++j)
        if (p[j] < x[i])
            swap(p[j], x[i]);

对称性! 我们在用 x[i] 操作 p 序列, 然后问每个 x[i] 最终变成了多少.

那么, 把 x 看成标记, 用小根堆维护 p 即可.

时间复杂度 .

有点卡常......