[六省联考2017]相逢是问候

Posted by Panda2134's Blog on March 14, 2018

day1 没上200……不应该啊……正常点的话215应该没问题?

题意

给定一个长为 $n (n \le 10^5)$ 的序列,要求支持 2 个操作:

  1. 把某个区间每个元素 $a_i$ 换成 $c^{a_i}$ ,其中 $c$ 是给定常数。
  2. 求区间和

思路

PoPoQQQ大爷:这……这不是……上帝和集合的正确用法吗?

然而我做过上帝和集合的正确用法,却没能做出来这题 >.<

有扩展欧拉定理: 根据上帝和集合的正确用法,这个可以递归下去求,由于 $\varphi(n)$ 每次至少折半,复杂度是 $O(\lg n)$ 级别的。

考试的时候,总是在想:在线段树上面记录什么信息,能够一次执行一个区间的递归求值操作呢?如果只记录加了多少次的话,每次求和就得暴力查,这样复杂度就是每次操作 $O(\lg n) - O(n\lg n)$ 的了……最后也没想出来,交的暴力,发现线性筛求 $\varphi(n)$ 被卡了QAQ

实际上,为什么不换个角度思考呢?与其说一次执行一个区间的递归求值,还不如每次暴力改,在 $O(\lg n)$ 次之后,那个位置原来的值是什么已经无关紧要了,因为递归下去出现了 $\text{mod } 1$ ,最后求出的值一定相同!于是就不用再修改了= =

我们来冷静分析一下复杂度。修改的话区间内每个元素暴力,所有元素最多改 $O(\lg n)$ 次,考虑序列所有元素,最坏复杂度是 $O(n \lg^3 n)$ (每次迭代+快速幂是 $O(\lg^2 n)$ 的),再算上每次在线段树上面分解区间的 $O(\lg n)$ ,总修改复杂度是 $O(n \lg^3 n + q_0 n) = O(n \lg^3 n)$ 的,均摊到每次修改是 $O(\lg^3n)$ 的。每次暴力改的时候维护下区间和,总查询复杂度是 $O(q_1 \lg n)$ 的。

哲♂学分析一下,发现复杂度出现了 $O(\lg n) - O(n\lg n)$ 这种东西,运用根号平衡的思想,也应该想到提高前一半复杂度,降低后一半复杂度?

其实这个思想和维护“区间开方-区间求和”也是类似的……

代码

好像还有一种把快速幂的 $O(\lg n)$ 去掉的方法?