CF1705E Mark and Professor Koro 题解

发布时间 2023-12-01 18:53:25作者: ShawyYum

题意:

给定一个长度为 $ n $ $ (1 \le n \le 2e5) $ 的序列,每次可以把两个相等的 $ a_i $ 和 $ a_j $ 合并为一个 $ a_i + 1 $ 。给定 $ q $ $ (1 \le q \le 2e5) $ 次修改,每次将 $ a_k $ 修改为 $ l $ ,求每次操作后合并到无法再合并时出现的最大数。其中,$ 1 \le a_i \le 2e5 $。

思路:

由于 $ 1 \le a_i \le 2e5 $ ,考虑从值域入手。将序列 $ a $ 视为一个数字 $ num $ ,则 $ a_i $ 为 $ num $ 二进制下第 $ a_i $ 位,从低位到高位依次进位。因此,问题转化为维护高精度二进制数字

每次将 $ a_k $ 修改为 $ l $ :相当于删除 $ a_k $ ,添加 $ l $ 。

删除 $ a_k $ :相当于 $ num $ 减去 $ 2^{a_k} $ ,相当于 $ num $ 二进制下第 $ a_k $ 位减去 $ 1 $ ,可能会向高位连续借 $ 1 $ ,直至高位第一个 $ a_{pos} = 1 $ 出现为止,借位结束后 $ a_{pos} = 0 $ , $ a_i = 1(i ∈ [k,pos - 1]) $ 。

添加 $ l $ :相当于 $ num $ 增加 $ 2^l $ ,相当于 $ num $ 二进制下第 $ l $ 位增加 $ 1 $ ,可能会向高位连续进 $ 1 $ ,直至高位第一个 $ a_{pos} = 0 $ 出现为止,进位结束后 $ a_{pos} = 1 $ , $ a_i = 0(i ∈ [k,pos - 1]) $ 。

考虑通过线段树维护上述过程:

由于 $ 1 \le n,a_i \le 2e5 $ ,考虑长度为 $ 2e5 $ 的序列 $ a $ 中所有元素都为 $ 2e5 $ ,一共进行 $ \log_ {2} {2e5} $ 次合并,出现的最大数不超过 $ 2e5 + 100 $ ,因此线段树的边界为 $ [1,2e5 + 100] $ 。

对于删除操作,查询 $ num $ 二进制下第 $ a_k + 1 $ 位至第 $ 2e5 + 100 $ 位之间,最靠近第 $ a_k $ 位的最大值 $ pos $ ,对 $ a_{pos} $ 进行单点修改,对 $ [a_k,pos - 1] $ 进行区间修改即可。

对于添加操作,查询 $ num $ 二进制下第 $ a_k + 1 $ 位至第 $ 2e5 + 100 $ 位之间,最靠近第 $ a_k $ 位的最小值 $ pos $ ,对 $ a_{pos} $ 进行单点修改,对 $ [a_k,pos - 1] $ 进行区间修改即可。