LG7447 [Ynoi2007] rgxsxrs

发布于 2021-07-28  1.01k 次阅读


题目链接

题意

给定一个长为 $n$ 的序列 $a$,需要实现 $m$ 次操作:

  1. 1 l r x: 表示将区间 $[l,~r]$ 中所有 $>x$ 的元素减去 $x$。
  2. 2 l r: 表示询问区间 $[l,~r]$ 的和,最小值,最大值。

强制在线,$n,~m \le 5 \times 10^5,~a_i \le 10^9$。

分析

考虑以 2 进制进行值域分块,第 $i$ 块开动态开点线段树存储所有满足 $a_i \in [2^i,~2^{i+1})$ 的位置的信息。

考虑对于 1 操作,我们枚举每一个值域块,将该块内下标在 $[l,~r]$ 之间的元素拿出,进行判断:

  • 若该块所有元素值均 $>x$: 对这些元素打上 $-x$ 标记即可。
  • 若该块所有元素值均 $\le x$: 不进行任何操作。
  • 若不满足上述两个条件: 在线段树上向子树递归进行修改操作。

考虑分析此处暴力递归的时间复杂度,容易发现在某块内每次成功的修改都会让被修改元素减少至少一半。显然单个元素最多被修改 $\log_2 a_i$ 次,因此全局总共花在暴力递归上的复杂度为 $O(n \log_2 a_i)$。

在每次修改后,一些 $a_i$ 值减小后可能会因为过小而需要被分配到编号更小的块中,我们可以在线段树每个节点上维护子树最小值,每次修改完成后暴力二分找出过小的位置,将其从当前块线段树上暴力拆出,插入到更小编号的块的线段树内。考虑此操作总时间复杂度,因为一共只有 $\log_2 a_i$ 个块而每次结点只会从当前块到编号更小的块,因此每个元素最多只会在块间移动 $\log_2 a_i$ 次,所以花在此操作上的全局总时间复杂度为 $O(n \log_2 a_i \log_2 n)$。

对于 2 操作,我们只要将每块内的 $[l,~r]$ 部分答案取出合并起来就可以了。

此时总时间复杂度 $O(n \log_2 n \log_2 a_i)$,空间复杂度 $O(n \log_2 a_i)$。

我们发现这样的空间复杂度不足以通过此题,我们考虑线段树底层以 $\log_2 a_i$ 块长分块,则每棵线段树叶子节点数量为 $\frac {n} {\log_2 a_i}$,空间复杂度降为 $O(n)$,可以通过此题。

由于此题较卡常,可以考虑根据代码运行情况调整分块的进制和线段树底层分块块长。

代码

本人代码使用指针版动态开点线段树,线段树底层块内使用链表储存,14 进制值域分块,线段树底层块长 500(由于常数比较大,小块长一直 TLE 一个点,但是这个接近 $\sqrt n$ 的块长出乎意料地跑得飞快)。

View On Github


我缓慢吐出一串啊吧啊吧并不再想说话