分块 + two pointer.
一个数被加入到队列 $i$ 中后,队列 $i$ 再进行 $a_i$ 次 push 操作,这个数就会被 pop 出来.
考虑对于每次操作 $j$ ,求出一个 $ed(j)$ ,表示在进行了 $(j,ed(j)]$ 内的操作后,操作 $j$ 加入的每个 $x$ 都被 pop 出来了.
对于同一个 $x$ ,将 $(j,ed(j)]$ 这些区间取并,就可以得到这个 $x$ 对每次询问的贡献,那么只需要设法求出每个 $ed(j)$ .
将序列每 $\sqrt n$ 个元素分成一块,对于每次操作 $(l_j,r_j,x_j)$ ,分别考虑整块部分的 $i$ 和边角部分的 $i$ 对 $ed(j)$ 的贡献.
枚举每个整块,对于包含了这一块的所有 $j$ ,每个该块中的 $x_j$ 被完全弹出的时间是递增的,可以用 two pointer 处理.
记录两个指针 $j,k$ ,表示当前考虑了操作 $(j,k]$ 带来的影响.
设 $b(i)$ 表示第 $i$ 个队列再被 push $b(i)$ 次, $x_j$ 就会被弹出,记录一个 $cov$ 表示这一块被整体 pop 了 $cov$ 次.
$k$ 增大,加入一个操作时,若它完整覆盖了该块, $cov$ 增加 $1$ ,否则,将这次操作与这一块的交集部分的 $b(i)$ 都减少 $1$ .
$b(i)$ 初始都为对应的 $a(i)$ ,维护一个 $mx=\max b(i)$ ,当 $mx\le cov$ 时,说明已被完全弹出, $k$ 可以去更新 $ed(j)$ .
$j$ 增大,撤销一个操作时,维护方法类似,将 $cov$ 减少 $1$ ,或将交集部分的 $b(i)$ 都增加 $1$ .
每次修改 $cov$ 是 $O(1)$ 的,修改交集部分的 $b(i)$ 是 $O(\sqrt n)$ 的.
每个操作最多完全覆盖 $O(\sqrt n)$ 个整块,最多与 $2$ 个整块有交集,但未完全覆盖,于是这部分时间复杂度为 $O(m\sqrt n)$ .
再来考虑边角部分的贡献,需要在处理整块贡献的同时维护出一些信息.
设 $s(i)$ 表示前 $i$ 次操作完全覆盖了当前块 $s(i)$ 次.
设 $c(i)$ 表示第 $i$ 个完全覆盖当前块的操作编号.
设 $d(i)$ 表示第 $i$ 个与当前块有交集,但未完全覆盖的操作编号.
设 $e(i)$ 表示第 $e(i)$ 次操作结束后,恰好完全覆盖了该块 $i$ 次.
枚举块内每个位置 $i$ ,考虑它作为边角部分被覆盖的贡献.
用 two pointer 维护两个指针 $j,k$ ,表示当前考虑了操作 $(d(j),d(k)]$ 的影响,并维护 $mx$ 表示 $i$ 被覆盖的次数.
向后跳时,整块覆盖的次数可以由前缀和 $s$ 算出,交集部分覆盖的次数可以直接由 $d$ 存储的操作编号判断.
当 $mx\le 0$ 时,说明位置 $i$ 上的 $x_j$ 已经被 pop 出去了,此时可以更新答案.
若 $mx=0$ ,说明恰好是由操作 $d(k)$ 弹出去的,否则是 $d(k)$ 之前整块操作弹出的,用维护的 $c,e$ 数组可以找出答案.
设第 $i$ 块的数组 $d$ 大小为 $t_i$ ,则这部分的时间复杂度为 $O(\sum \sqrt n\cdot t_i)=O(\sqrt n\cdot \sum t_i)=O(m\sqrt n)$ .
于是整个算法的时间复杂度为 $O(m\sqrt n)$ .
1 | //%std |