1. 成都站的这道G题凭什么让人赛后还念念不忘2024年ICPC成都区域赛打完之后我们队内复盘群里讨论最多的不是金牌线也不是某道压轴题而是G题Expanding Array。原因很简单它表面看起来是一道每次把数组变长的模拟题实际上是一道数学建模 数据结构维护的复合题。如果你上手就开一个vector老老实实地逐元素展开数据稍微大一点就爆时间、爆内存现场不少队伍就是在这里卡了半个多小时最后连暴力对拍都没来得及写。先说说这道题在整场比赛里的定位。ICPC区域赛的题号不严格按难度递增但G题通常处在铜牌区以上队伍需要拿下的区间比签到题多一层思维转换又不像最后几题那样依赖冷门算法。Expanding Array正好卡在这个位置。它的难点不在于某个高深算法而在于你愿不愿意做那个关键建模把数组真的变长了转换成每个原始元素携带一个膨胀次数数组的长度、总和、单点值全部用公式算出来而不是真的去维护那个不断膨胀的序列。赛后我把题意和做法重新完整梳理了一遍发现这套东西的复习价值非常高。它同时涉及二项分布计数、懒标记线段树、按位置二分定位三个模块任何一个单独拿出来都是经典题组合在一起就成了区域赛G题的难度。而且这套把指数增长的过程用数学摊平的思路放到2025年西安区域赛的备赛周期里也大概率用得上。下面我把完整推导链和可编译的C17实现写出来适合正在备战区域赛、想补数据结构思维的同学参考。2. 先把膨胀规则固定下来再谈做法2.1 我整理的题意版本现场题面的官方英文描述我记不全这里按我印象中通用版本重述不影响核心做法。初始给定一个长度为N的数组a[1..N]接下来有Q个操作类型1 l r对原始数组下标在[l, r]中的所有元素各执行一次膨胀操作类型2 p查询当前数组中第p个位置的值类型3 l r查询当前数组中位置区间[l, r]的元素和结果对1e97取模。膨胀操作的定义是把当前数组中的一个元素x替换成两个相邻元素x和x1。替换后这两个元素仍然占据原来x的位置所以数组的整体顺序不会乱只是总长度增加了1。如果你的考场版本在区间定义上有细微差别比如操作的是当前数组的下标而不是原始下标那需要在数据结构上额外做分裂维护我会在第4节末尾单独说明。核心的数学部分完全一致。2.2 为什么直接模拟必然爆炸如果只膨胀几次直接模拟没有问题但膨胀是指数增长的。一个初始值为x的元素膨胀t次之后不是长出t个后代而是长出2^t个。Q稍微大一点最终数组长度就会超过内存上限。更麻烦的是每一次区间膨胀会让区间内每个元素各自分裂数组长度和查询位置都在动态变化普通数组结构根本无法维护。所以必须放弃把最终数组建出来的思路转而研究一个元素经过多轮膨胀之后它的后代长什么样、总和是多少。只要能回答这两个问题剩下的就是怎么高效地对原始下标做区间更新、按位置做查询。2.3 单点反复膨胀的形态二项式系数我们先看单个元素x连续膨胀t轮的结果。用偏移量表示即把x记为0前几轮长这样t展开后的偏移序列长度0[0]11[0, 1]22[0, 1, 1, 2]43[0, 1, 1, 2, 1, 2, 2, 3]8这个序列有两个规律。第一值为d的元素出现C(t, d)次也就是二项式系数t3时偏移0出现1次偏移1出现3次偏移2出现3次偏移3出现1次。第二序列第r个位置r从0开始的偏移量恰好等于r的二进制表示中1的个数也就是popcount(r)。第二个规律证明很简单用归纳法。假设第t轮的第k个位置偏移量是popcount(k)那么生成第t1轮时每个元素e被替换成e和e1。第t1轮的下标2k对应原第k个元素复制出来的前半部分偏移量是popcount(k)下标2k1对应后半部分偏移量是popcount(k)1。而popcount(2k)popcount(k)popcount(2k1)popcount(k)1正好吻合。这个观察是整个题目最重要的跳板你不需要真的存储2^t个元素只需要在需要回答某个位置时用popcount算一下当前位置的值就够了。2.4 单点总和的封闭公式一个初始值为x的元素膨胀t轮后总和对MOD取模等于多少利用二项式系数分布xd出现C(t, d)次所以总和是S(t) Σ C(t, d) × (x d) x × Σ C(t, d) Σ d × C(t, d)其中Σ C(t, d) 2^tΣ d × C(t, d) t × 2^(t-1)。于是S(t) x × 2^t t × 2^(t-1)t0时为x这个公式还有个递推验证方式膨胀一轮每个元素y变成y和y1总和从S变到2S个数。第t轮的元素个数是2^t所以S(t1)2S(t)2^t代进去恰好得到上面的封闭式。到这里问题的数学摊平就完成了每个原始元素i只需要维护一个膨胀次数t_i它的总贡献、长度、某个具体位置的值全都可以用t_i算出来。剩下的问题是怎么高效地对原始下标区间做t_i 1并且回答各种按位置的查询。3. 区间操作变成懒标记线段树需要维护哪三个量3.1 区间膨胀等价于膨胀次数区间加一上述模型里一次类型1操作[l, r]就是让i ∈ [l, r]的所有t_i增加1。这不是普通的区间加法因为每个元素贡献里t_i出现在指数上。如果用一个普通的区间加定值 维护区间和线段树根本没法下推懒标记。我们需要设计一种线段树节点上同时挂多个关联量让t_i整体加d这个操作对每个节点的聚合信息都能用O(1)公式更新。3.2 A、B、C三个聚合量是怎么来的对线段树的某个节点它管辖若干原始元素。为了能回答区间和我们要时刻知道这个节点内所有元素当前贡献的总和。由S(t)公式可知单点贡献分成两项x × 2^t和t × 2^(t-1)。于是很自然地定义三个聚合量A Σ a_i × 2^(t_i)B Σ t_i × 2^(t_i - 1)C Σ 2^(t_i)节点的总和就是(A B) mod MOD。这里C看起来有点冗余但后面你会发现没有它B的懒标记根本推不动。看t_i整体增加1的情况。逐项推导A变A每个2^(t_i)变成2^(t_i1)整体乘2所以A 2A。C变C同理C 2C。B变BB Σ t_i × 2^(t_i - 1)加1后变成B Σ (t_i 1) × 2^(t_i) 2Σ t_i × 2^(t_i - 1) Σ 2^(t_i) 2B C也就是说一次整体加1时B的新值不仅和B有关还和C有关。这就是必须在节点里额外维护C的原因。3.3 懒标记下推的完整推导如果某个节点累积了d次膨胀还没有下推那么在push时需要一次性把d传给两个儿子。上面的式子推广到dA A × 2^dC C × 2^dB Σ (t_i d) × 2^(t_i d - 1) 2^d × Σ t_i × 2^(t_i - 1) d × 2^(d - 1) × Σ 2^(t_i) B × 2^d C × (d × 2^(d - 1))所以只要预处理两张表pow2[d] 2^d mod MOD以及pow2half[d] d × 2^(d - 1) mod MOD任何一个节点收到懒标记d时都能在O(1)时间内把A、B、C全部更新。对于d1的特例就是A 2AB 2B CC 2C这组公式的优美之处在于它把指数层面的区间加转化成了聚合量层面的线性变换懒标记照常累积完全兼容标准的区间更新线段树。3.4 长度信息也要跟着翻倍饱和处理除了A、B、C位置查询还需要每个块的实时长度。原始元素i膨胀t_i次后对应块的长度是2^(t_i)。线段树节点上我们额外维护一个Len Σ 2^(t_i)也就是这个节点管辖区块的总长度。问题来了t_i最多能到Q2^Q早就溢出64位。我的处理办法是给Len设一个上限LIM 4e18略小于long long最大值所有加法、乘法都在达到上限后饱和截断。这个处理对查询是安全的因为所有查询位置p都不会超过1e18量级而一旦真实长度超过LIM饱和值LIM依然大于任何合法p比较关系不会出错。真正需要精确值的场景只发生在长度小于LIM时那时饱和加法不会启动。4. 位置查询在膨胀后的数组里二分定位块内公式解决一切4.1 用Len在树上二分找到位置落在哪个原始块膨胀后的数组天然按原始下标分成N块第i块长度是2^(t_i)块内元素的相对顺序就是第2.3节定义的序列顺序。要在当前数组里定位第p个位置只需要在线段树上利用Len做二分从根出发如果p小于等于左儿子管辖区块的总长度就进左儿子否则p减去左儿子总长度进右儿子。递归到叶子时就得到了对应的原始下标i以及p在块内的偏移位置q1-indexed。顺便还能在下降过程中累加当前块之前所有完整块的总贡献也就是那些块的(A B)之和。这个值在回答前缀和时直接可用省去一次额外的区间查询。4.2 块内第k个元素的值popcount(k - 1)定位到块i和块内位置q后这个元素的值等于a_i popcount(q - 1)。原因在前面证明过块内第r个位置r从0开始的偏移量就是popcount(r)。这个操作是O(1)的__builtin_popcountll一条指令就能算完。对比一下真的建出2^t长度的数组的做法这里的空间节省是指数级的。4.3 块内前缀和q × a_i 前q个popcount之和回答一次区间和查询当前位置[l, r]的元素和等价于前缀和函数F(p)相减。F(p) 完整块贡献之和 最后一个不完整块的块内前缀。不完整块的贡献需要算Σ_{r0}^{q-1} (a_i popcount(r)) q × a_i Σ_{r0}^{q-1} popcount(r)。前半部分O(1)后半部分需要一点数位技巧。观察0到q-1这些数里第b位从低到高上有多少个1。每个完整的周期长度是2^(b1)一个周期内第b位有2^b个1。设full q / 2^(b1)rem q % 2^(b1)那么这一位的贡献是full × 2^b max(0, rem - 2^b)。对所有b从0到62累加即可单次计算O(60)。到这里所有查询都不需要真实展开数组全部转化为线段树上的O(log N)定位加上O(1)或O(60)的公式计算。5. 完整实现一份能直接编译跑的C17代码5.1 核心代码我把自己赛后重写的版本贴在下面。整体结构是递归线段树数组开4N懒标记、饱和长度、位置二分都在里面。#include bits/stdc.h using namespace std; using ll long long; const ll MOD 1000000007LL; const ll LIM 4000000000000000000LL; // 4e18 饱和上限 int N, Q; vectorll base; vectorll A, B, C, Len, lazy; vectorll pow2, pow2half; ll addcap(ll x, ll y) { if (x LIM || y LIM || x LIM - y) return LIM; return x y; } ll mulcap(ll v, ll d) { if (v LIM) return LIM; if (d 63) return LIM; __int128 t (__int128)v d; if (t LIM) return LIM; return (ll)t; } // sum_{i0}^{q-1} popcount(i) mod MOD ll sumpop(ll q) { __int128 ans 0; for (int b 0; b 63; b) { ll half 1LL b; ll period half 1; ll full q / period; ll rem q % period; ans (__int128)full * half; if (rem half) ans rem - half; } return (ll)(ans % MOD); } void apply(int p, ll d) { if (d 0) return; lazy[p] d; A[p] A[p] * pow2[d] % MOD; B[p] (B[p] * pow2[d] C[p] * pow2half[d]) % MOD; C[p] C[p] * pow2[d] % MOD; Len[p] mulcap(Len[p], d); } void push(int p) { if (lazy[p]) { apply(p 1, lazy[p]); apply(p 1 | 1, lazy[p]); lazy[p] 0; } } void pull(int p) { A[p] (A[p 1] A[p 1 | 1]) % MOD; B[p] (B[p 1] B[p 1 | 1]) % MOD; C[p] (C[p 1] C[p 1 | 1]) % MOD; Len[p] addcap(Len[p 1], Len[p 1 | 1]); } void build(int p, int l, int r) { lazy[p] 0; if (l r) { A[p] base[l] % MOD; B[p] 0; C[p] 1; Len[p] 1; return; } int m (l r) 1; build(p 1, l, m); build(p 1 | 1, m 1, r); pull(p); } void update(int p, int l, int r, int ql, int qr) { if (ql l r qr) { apply(p, 1); return; } push(p); int m (l r) 1; if (ql m) update(p 1, l, m, ql, qr); if (qr m) update(p 1 | 1, m 1, r, ql, qr); pull(p); } struct Info { int idx; ll pos; // 块内位置1-indexed ll prefSum; // 该块之前所有完整块贡献之和 (AB) mod MOD }; Info locate(int p, int l, int r, ll pos, ll prefSum) { if (l r) return {l, pos, prefSum}; push(p); int m (l r) 1; ll leftLen Len[p 1]; if (pos leftLen) return locate(p 1, l, m, pos, prefSum); ll addSum (A[p 1] B[p 1]) % MOD; return locate(p 1 | 1, m 1, r, pos - leftLen, (prefSum addSum) % MOD); } ll prefixSum(ll pos) { if (pos 0) return 0; Info in locate(1, 1, N, pos, 0); ll q in.pos; ll inside (q % MOD) * (base[in.idx] % MOD) % MOD; inside (inside sumpop(q)) % MOD; return (in.prefSum inside) % MOD; } ll valueAt(ll pos) { Info in locate(1, 1, N, pos, 0); ll rank in.pos - 1; return base[in.idx] __builtin_popcountll((unsigned long long)rank); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N Q; base.assign(N 1, 0); for (int i 1; i N; i) cin base[i]; A.assign(4 * N 5, 0); B.assign(4 * N 5, 0); C.assign(4 * N 5, 0); Len.assign(4 * N 5, 0); lazy.assign(4 * N 5, 0); pow2.assign(Q 1, 1); pow2half.assign(Q 1, 0); for (int i 1; i Q; i) { pow2[i] pow2[i - 1] * 2 % MOD; pow2half[i] (ll)i * pow2[i - 1] % MOD; } build(1, 1, N); while (Q--) { int op; cin op; if (op 1) { int l, r; cin l r; update(1, 1, N, l, r); } else if (op 2) { ll pos; cin pos; cout valueAt(pos) % MOD \n; } else { ll l, r; cin l r; ll ans (prefixSum(r) - prefixSum(l - 1) MOD) % MOD; cout ans \n; } } return 0; }5.2 复杂度分析建树O(N)。每次区间膨胀O(log N)因为只在覆盖到的节点上整体应用懒标记。每次位置查询或前缀和查询O(log N)定位加上sumpop的O(60)整体O(log N 60)。空间上线段树四个主数组加懒标记数组都是4N量级两张预处理表是Q量级。整体内存非常宽裕。实际操作中Q到2e5、N到1e5的规模下这个程序跑得飞快现场赛的时限完全不是问题。5.3 必须注意的边界与溢出点我写代码和调试时踩过几个坑列出来帮你省时间。第一t_i 0时B项必须为0。初始建树时B[p] 0不要手滑写成别的。pow2half[0]也要专门置0因为公式d × 2^(d - 1)在d0时没有意义。第二Len的饱和处理。不要把LIM设成LLONG_MAX因为两个大数相加会溢出设成4e18留出加法余量配合addcap里的x LIM - y判断最稳。mulcap里要对d 63单独判断否则左移超过64位是未定义行为。第三sumpop的中间结果会超过long long。q最大可以到4e18full × half的量级能到1e38必须用__int128累加最后再取模。我一开始用long long写小数据对拍全对大数据一跑就飘查了半小时才定位到这里。第四locate函数里要先push再读左儿子的Len。否则懒标记还压在父节点上儿子的Len是旧值二分定位会出错。这也是懒标记线段树做树上二分最容易漏的细节。第五如果官方题面的类型1给的区间是当前数组的下标而不是原始下标上面的线段树就要改成平衡树或分裂结构每个原始块是一个节点膨胀一段区间时先把节点按位置切开再对中间的整块应用懒标记。这样复杂度仍旧是O(log N)级别但实现量会明显变大。好在我印象里成都这题的类型1约束在原始下标上复杂度压力小很多。6. 这道G题能带走的三个通用套路6.1 看到数组会长大先想数学摊平而不是模拟指数增长的模拟问题几乎不可能暴力做。Expanding Array给的启发是当每个元素的变化规则足够规整时先把单点t轮后的形态、长度、总和全部写成封闭公式再把所有操作翻译成某个参数区间加一。这个参数化摊平的思路在名为Expanding Array的题里体现得淋漓尽致同类问题里也很常见——凡是每次把元素替换成若干个新元素的过程优先考虑用组合计数压缩状态。6.2 懒标记可以挂多个关联量但要保证整体加d能联动很多人对懒标记的理解停留在区间加、区间和两层。这道题展示了更一般的形式只要你能找到一个聚合向量X使得对区间内所有参数加d时X M_d × X是线性变换就可以用懒标记。A、B、C三个量的组合正是为了凑出这个线性关系。以后遇到区间内每个数变成它的函数这类更新先试着找一组能封闭的量比硬维护原值聪明得多。6.3 动态数组的定位问题可以用块长 块内公式解耦位置查询最怕的就是数组长度一直在变。这里的解法是把数组看成块序列每个块的长度用公式快速算块内再单独设计查询公式。这样定位到块和计算块内答案两个问题完全解耦各自用擅长的方法解决。类似的技巧在可持久化数组、带分裂的平衡树题目里都能看到影子。7. 留给2025年西安站的备赛建议成都这场打完我的最大体会是区域赛G题考的不是你会多少冷门算法而是你能不能在一个小时内完成识别模型 设计聚合量 写出正确代码的完整链路。Expanding Array正好是这三个环节都很标准的题建议把它当成一轮完整的模拟赛复盘来做——先自己推导A、B、C的公式再独立写线段树最后用随机数据对拍验证。我自己的做法是把代码留到今天隔了两周重新手写一遍第二次明显顺畅很多。备赛2025年西安站的话这类组合计数 懒标记线段树的题目值得单独整理一个题单。你可以把近期各区域赛的G题、H题都拉出来重点看它们怎样把指数增长、区间更新、位置查询缝合在一起。真正上考场的时候如果一道题卡了超过四十分钟先跳过做后面的题留最后二十分钟再回头对拍暴力版本。我在成都赛场上就是靠这个节奏稳住心态才在结束前把Expanding Array的朴素做法对拍通过的。这道题带给我的不只是这一份代码更是一整套怎么把一个看起来会无限膨胀的问题压进有限的线段树里的思考方式。