LeetCode 1622. 奇妙序列Fancy Sequence光看名字就透着一股不按套路出牌的味道。这道题在周赛里是典型的硬骨头四个操作里有两个是全体生效append 却总在最后冒出来捣乱。我最早看到它时第一反应是直接开个数组模拟三分钟写完然后被评测数据教做人。这篇文章我打算把完整的思考链路写出来——从延迟标记、乘法逆元到 mul0 时的归一化再到线段树的精简实现。适合已经会基本线段树、想彻底搞懂这道 hard 的读者也适合准备周赛、想补一补全局批量更新 单点查询这类套路的选手。1. 奇妙在哪里四个操作读完我猜你已经开始写模拟了1.1 题目到底让我们干什么原题让你实现一个Fancy类一共四个方法方法参数行为appendval在末尾追加一个值为 val 的元素addAllk给当前所有元素统一加 kmultAllk给当前所有元素统一乘 kgetIndexidx返回下标 idx 的元素对 1e97 取模后的值官方示例很朴实先append(2)序列变成 [2]再addAll(3)所有元素加 3变成 [5]再multAll(2)所有元素乘 2变成 [10]最后getIndex(0)应该返回 10。看起来就像小学生四则运算但真正坑人的是题目最后一行数据规模操作总数最多到 1e5。这意味着你绝对不能在每次addAll或multAll的时候老老实实遍历一遍当前所有元素。还有个小细节题目要求所有结果对 1e97 取模。这个模数不是随便选的后面算逆元的时候全靠着它是素数这一点才能用费马小定理。1.2 直接模拟的死路O(nq) 的复杂度瓶颈很多人在周赛里挂在这道题上不是因为不会而是因为第一版代码写得太直觉了维护一个vectorlong long arrappend就 push_backaddAll就 for 循环 kmultAll就 for 循环 * kgetIndex直接返回arr[idx]。这个方案本地跑小样例没问题一提交就超时。你只需要构造一个最朴素的序列前 5 万次全是append后 5 万次全是addAll。到第 5 万次addAll的时候数组长度已经变成了 5 万每次addAll都要遍历 5 万个元素总操作量大约是 25 亿。如果把append和addAll交替穿插例如append、addAll、append、addAll循环来总遍历次数会达到 50 亿级别。按 1e8 次简单运算每秒估算几十秒都不一定跑得完评测机根本不可能给你这个时间。所以看到全体修改 单点查询的组合第一反应该永远是延迟更新把批量操作记在账本上而不是立刻改动每一个元素。1.3 一个反直觉的结论addAll 其实可以不碰任何元素那么延迟更新的直觉从哪来呢先看一个简化版如果只有addAll和getIndex你只需维护一个全局变量addaddAll就add kgetIndex就返回arr[idx] add。如果只有multAll和getIndex你只需维护全局变量mulgetIndex就返回arr[idx] * mul。两个操作同时出现时问题就变成了怎样用一个统一表达式描述先加后乘和先乘后加对每个元素的不同影响这时候最好的办法是给每个元素定义一个基准值base[i]让真实值满足下面的形式real[i] base[i] * mul add只要这个式子成立那么multAll和addAll本质上都只是修改mul和add两个旋钮完全不需要碰数组里的任何元素。这就是解决整道题的数学地基。2. 全局变换 x → x·mul add两个变量解决所有批量更新2.1 为什么可以延迟乘法对加法的分配律把当前所有历史操作浓缩成两个全局变量mul和add并规定每个元素i的真实值为real[i] (base[i] * mul add) mod MOD初始时mul 1、add 0。此时如果append(val)base[i]就等于 val真实值就是 val和直觉一致。你可以把base[i]想象成元素在初始坐标系里的坐标而mul和add合起来是从初始坐标系到当前世界坐标系的仿射变换。无论后续来了多少次全局加法、全局乘法我们都不用去重画每个点只要更新这个变换本身。为什么能做到因为乘法对加法有分配律任何对全体元素同时做相同的仿射变换都可以浓缩成一个mul加一个add。2.2 multAll 的唯一正解mul 和 add 同步放大执行multAll(k)时每个元素的真实值都要乘 k。代入公式real[i] * k (base[i] * mul add) * k base[i] * (mul * k) (add * k)所以正确做法是mul mul * k mod MODadd add * k mod MOD注意add必须跟着乘 k否则会漏掉过去发生的加法在乘 k 之后应该被放大这一层。举个例子base[i]2、mul1、add4真实值是 6。执行multAll(2)后应该得到 12。如果只把mul改成 2 而add保持 4算出来2*248错了把add也改成 8才是2*2812。这个乘法要连带 add 一起乘的点写第一版代码的时候非常容易漏。2.3 addAll 只需改 add并亲手验证一个三连操作执行addAll(k)时真实值加 kreal[i] k base[i] * mul (add k)因此只需要add (add k) mod MODmul和base一概不动。这地方确实反直觉一个作用于全体元素的操作居然只需要改一个变量。我们用官方示例完整验证一遍。初始mul1, add0append(2)base[0]2真实值2*102addAll(3)add3真实值2*135multAll(2)mul2, add6真实值2*2610getIndex(0)返回 10全程没有遍历任何数组也没有更新base[0]。所以在这道题里真正的难点其实不是这两个全体操作而是append一个刚出生的元素怎么被塞进这套已经运行了很久的全局变换坐标系里3. append 一票否决新元素需要逆元才能纳入坐标系3.1 基准值 base[i] 的推导一个一元一次方程append(val)追加的元素真实值当然必须严格等于 val。可它又要和当前的全局mul、add兼容。换句话说我们要解一个一元一次方程base_new * mul add ≡ val (mod MOD)解出来就是base_new ≡ (val - add) * inv(mul) (mod MOD)这里的inv(mul)是mul在模 1e97 意义下的乘法逆元。举个例子当前mul2, add0序列里所有旧元素都已经翻过倍了这时append(5)如果直接把base记为 5那么getIndex会算出来5*2010明显错误。正确做法是先算base_new(5-0)*inv(2)。在模 1e97 下inv(2)500000004于是base_new500000004查询时(500000004*20)%MOD5。也就是说base里存的并不是元素看起来长什么样而是它在初始坐标系里的坐标。这个坐标可能是负数模意义下的数、看起来完全不像最终值但它和全局变换组合之后一定能还原出正确答案。3.2 乘法逆元与费马小定理为什么 MOD 选 1e97很多新手看到inv(mul)就慌了以为要写扩展欧几里得。其实完全不用。1e97 是素数所以任何非零数在模意义下都有逆元并且可以用费马小定理直接求a^(MOD-1) ≡ 1 (mod MOD)两边同时除以 a得到a^(MOD-2) ≡ inv(a) (mod MOD)也就是一个快速幂就能搞定的东西long long modPow(long long a, long long e) { long long res 1; while (e 0) { if (e 1) res res * a % MOD; a a * a % MOD; e 1; } return res; }求逆元就是modPow(x, MOD-2)循环 30 次左右append 最多 1e5 次总成本 3e6 次乘法上下宽松得很。这也就是为什么题目选 1e97 而不是随便什么模数——它几乎是直接暗示你用逆元。3.3 真正的魔鬼mul0 时逆元蒸发逆元有一个致命前提你只能对非零数求逆。一旦mul在模意义下变成 0inv(mul)直接不存在append公式当场炸掉。这不是什么边角理论。比如操作序列append(2)然后multAll(1000000007)。因为val % MOD 0执行后mul0, add0此时序列里所有元素真实值都是 0。如果再append(1)按照公式(1 - 0) * inv(0)完全没法算。更隐蔽的是多步积累multAll(2)、multAll(5)、multAll(1000000007)三步之后mul照样变成 0。第一次遇到这个用例时我以为是代码里的临时 bug后来才发现这是数学层面的坑。要爬出去就得先想明白mul0的时候旧元素到底变成了什么样子4. mul0 归一化把旧元素全部按真实值落地4.1 为什么 mul0 时所有旧元素都长一个样回到核心公式real[i] base[i] * mul add当mul 0时第一项base[i] * 0直接消失于是real[i] add注意这里说的是所有旧元素的真实值都等于同一个add跟它们过去的base是多少完全无关。这绝境反而成了突破口既然旧元素全都等于add那我就可以一次性把它们的base全部改成add然后把全局变换重置为最干净的状态mul1, add0。这样一来旧元素真实值仍然是add而系统回到了可以用正常逆元公式的状态。我管这个过程叫归一化。4.2 归一化的操作定义与例子归一化分三步如果元素个数n 0把base[0..n-1]这个区间统一赋值为add令mul 1令add 0。之后再做append(val)就直接把base_new设为 val 就行因为(val - 0) * inv(1) val。完整推一个例子操作序列是append(2), multAll(0), addAll(3), append(4)。append(2)mul1, add0, base[0]2真实值 2multAll(0)mul0, add0所有元素真实值 0addAll(3)add3所有元素真实值都是 3append(4)发现mul0触发归一化。区间[0,0]赋值为 3mul1, add0然后 append 得到base[1]4最后序列里real[0]3、real[1]4完全符合历史操作。如果mul0期间还混了其他操作比如addAll(3)之后再来一个multAll(2)那么add会被更新成 6下次归一化时区间赋值用的就是 6依然正确。4.3 不归一化行不行聊聊最坏情况退化有人会说归一化不就是把旧元素全部遍历一遍改成 add 吗我就每次append前 O(n) 扫一遍总复杂度也没多夸张吧还真能卡死。构造一个专门针对这种写法的用例反复执行append(1)和multAll(0)。第一次append前归一化涉及 0 个元素第二次涉及 1 个第三次涉及 2 个到第 q/2 次就涉及 q/2 个。总开销大约(q/2)^2 / 2又是 1e9 这个量级。换句话说如果只是把遍历归一化当成补丁复杂度照样会退化到跟直接模拟一个量级。正确思路是把这个把一段区间统一改成某个值的操作交给能做到 O(log n) 的区间数据结构。于是线段树登场了。5. 线段树实现区间赋值 单点查询比想象中更简单5.1 只需要 lazy 标记不需要区间和回头数一数我们需要什么操作归一化要把[0, n-1]整体赋值为同一个addappend要把下标 n 这个点设为某个值getIndex要查询下标 i 的值。这是一个非常标准的区间赋值 单点修改 单点查询模型。线段树每个节点只需要维护一个 lazy 标记就够了连区间和都不用维护。约定lazy[p] -1这个区间没有被整体赋值过需要往下看子节点lazy[p] k这个区间内所有位置当前的值就是 k。区间赋值时只要当前节点区间被完全覆盖就打上这个标记不用递归到叶子。单点修改或查询时把路径上的标记往下推。代码量比带区间和的线段树少一半写起来不容易乱。5.2 C 实现Fancy 类完整代码下面是一个可运行的 C 核心实现我把MOD定为1e97所有乘法用long long防溢出。线段树大小直接按最大操作次数 100005 开class Fancy { private: static const long long MOD 1000000007LL; static const int MAXN 100005; int n 0; long long mul 1, add 0; vectorlong long lazy; void push(int p) { if (lazy[p] ! -1) { lazy[p 1] lazy[p]; lazy[p 1 | 1] lazy[p]; lazy[p] -1; } } void rangeSet(int p, int l, int r, int ql, int qr, long long val) { if (ql r || qr l) return; if (ql l r qr) { lazy[p] val % MOD; return; } push(p); int mid (l r) 1; rangeSet(p 1, l, mid, ql, qr, val); rangeSet(p 1 | 1, mid 1, r, ql, qr, val); } void pointSet(int p, int l, int r, int idx, long long val) { if (l r) { lazy[p] val % MOD; return; } push(p); int mid (l r) 1; if (idx mid) pointSet(p 1, l, mid, idx, val); else pointSet(p 1 | 1, mid 1, r, idx, val); } long long pointQuery(int p, int l, int r, int idx) { if (l r) return lazy[p] -1 ? 0 : lazy[p]; push(p); int mid (l r) 1; if (idx mid) return pointQuery(p 1, l, mid, idx); return pointQuery(p 1 | 1, mid 1, r, idx); } long long modPow(long long a, long long e) { long long res 1; while (e 0) { if (e 1) res res * a % MOD; a a * a % MOD; e 1; } return res; } long long inv(long long x) { return modPow((x % MOD MOD) % MOD, MOD - 2); } public: Fancy() : lazy(4 * MAXN, -1) {} void append(int val) { if (mul 0) { if (n 0) rangeSet(1, 0, MAXN - 1, 0, n - 1, add); mul 1; add 0; } long long baseVal ((val % MOD - add MOD) % MOD) * inv(mul) % MOD; pointSet(1, 0, MAXN - 1, n, baseVal); n; } void addAll(int k) { add (add k) % MOD; } void multAll(int k) { mul mul * (k % MOD) % MOD; add add * (k % MOD) % MOD; } int getIndex(int idx) { long long baseVal pointQuery(1, 0, MAXN - 1, idx); return (baseVal * mul add) % MOD; } };这里的逻辑顺序是append里如果发现mul 0先归一化再把新元素放进线段树addAll和multAll完全不动线段树getIndex永远用baseVal * mul add还原真实值。5.3 边界条件清单与复杂度结论把容易踩的地方集中列一下所有中间计算用long long。mul * k和add * k最坏接近 1e18long long刚好能装下。(val - add)可能是负数必须先加MOD再取模否则乘逆元后结果会错。求逆元只在mul ! 0时进行。append里mul 0的分支会先归一化归一化后mul一定是 1所以后面的inv(mul)是安全的。multAll(0)会把mul和add一起清零此时所有旧元素真实值都是 0这属于正常状态不需要特殊处理等append时再归一化即可。归一化时如果n 0不要执行区间赋值否则会出现空区间。上面的代码里已经用if (n 0)挡住了。新append的位置 n 不在归一化区间[0, n-1]内所以不会被旧标记污染。复杂度方面操作时间复杂度appendO(log MAXN log MOD)addAllO(1)multAllO(1)getIndexO(log MAXN)空间复杂度 O(MAXN)。整体来说每个操作都在对数级别1e5 次操作完全没问题。自测时可以重点试这几个用例操作序列预期结果append(2), addAll(3), multAll(2), getIndex(0)10append(2), multAll(0), addAll(3), append(4), getIndex(0), getIndex(1)3, 4append(1), multAll(1000000007), getIndex(0)0append(5), multAll(2), append(5), getIndex(1)5append(5), multAll(2), addAll(3), append(5), getIndex(1)5最后一个用例最容易想错addAll(3)发生在append(5)之前所以新追加的元素不应该继承这 3getIndex(1)仍然应该是 5。而append里用(val - add) * inv(mul)抵消全局add恰好能保证这一点。我最早写这道题时用的还是数组 每次 append 前 if(mul0) 整个数组归一的方案本地样例全过一提交就超时。后来想通mul0 意味着旧元素真实值全部坍缩成 add把它当成一个区间赋值问题用带 lazy 的线段树一压代码反而比原来更短。建议读者自己把上面几个例子手推一遍尤其是 mul0 之后连续 addAll、multAll、再 append 的流程。这类题只要你把归一化这一步想清楚后面基本就是套公式不会再翻车。