【题目来源】AcWing1277. 维护序列 - AcWing题库【题目描述】老师交给小可可一个维护数列的任务现在小可可希望你来帮他完成。有长为N NN的数列不妨设为a 1 , a 2 , … , a N a_1,a_2,…,a_Na1​,a2​,…,aN​。有如下三种操作形式把数列中的一段数全部乘一个值把数列中的一段数全部加一个值询问数列中的一段数的和由于答案可能很大你只需输出这个数模P PP的值。【输入】第一行两个整数N NN和P PP第二行含有N NN个非负整数从左到右依次为a 1 , a 2 , … , a N a_1,a_2,…,a_Na1​,a2​,…,aN​第三行有一个整数M MM表示操作总数从第四行开始每行描述一个操作输入的操作有以下三种形式操作1 111 t g c表示把所有满足t ≤ i ≤ g t≤i≤gt≤i≤g的a i a_iai​改为a i × c a_i×cai​×c操作2 222 t g c表示把所有满足t ≤ i ≤ g t≤i≤gt≤i≤g的a i a_iai​改为a i c a_icai​c操作3 333 t g询问所有满足t ≤ i ≤ g t≤i≤gt≤i≤g的a i a_iai​的和模P PP的值。同一行相邻两数之间用一个空格隔开每行开头和末尾没有多余空格。【输出】对每个操作3 33按照它在输入中出现的顺序依次输出一行一个整数表示询问结果。【输入样例】7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7【输出样例】2 35 8【核心思想】问题分析给定长度为N NN的数列a 1 , a 2 , … , a N a_1, a_2, \ldots, a_Na1​,a2​,…,aN​需要支持两种区间修改操作区间乘c cc、区间加c cc和一种区间查询操作区间和模P PP。这是一个**线段树 懒标记Lazy Propagation**问题核心挑战在于两种修改操作的叠加与优先级处理。算法选择线段树Segment Tree将数列划分为O ( log ⁡ N ) O(\log N)O(logN)层区间结构支持区间修改和查询的O ( log ⁡ N ) O(\log N)O(logN)时间复杂度懒标记Lazy Tag延迟下放修改信息将多次区间修改的复杂度从O ( N ) O(N)O(N)降至O ( log ⁡ N ) O(\log N)O(logN)双懒标记维护同时维护加法懒标记a d d addadd和乘法懒标记m u l mulmul处理先乘后加的复合操作关键步骤建树递归构建线段树每个节点存储区间[ l , r ] [l, r][l,r]、区间和s u m sumsum、加法懒标记a d d 0 add 0add0、乘法懒标记m u l 1 mul 1mul1懒标记应用eval对节点区间[ l , r ] [l, r][l,r]应用操作( a d d , m u l ) (add, mul)(add,mul)时更新区间和s u m ← s u m × m u l ( r − l 1 ) × a d d sum \leftarrow sum \times mul (r - l 1) \times addsum←sum×mul(r−l1)×add更新懒标记m u l ← m u l n e w × m u l o l d mul \leftarrow mul_{new} \times mul_{old}mul←mulnew​×mulold​a d d ← a d d o l d × m u l n e w a d d n e w add \leftarrow add_{old} \times mul_{new} add_{new}add←addold​×mulnew​addnew​核心原理先乘后加新操作叠加在旧操作之上保持运算顺序懒标记下传pushdown将父节点的( a d d , m u l ) (add, mul)(add,mul)下传给左右子节点后清空父节点懒标记a d d ← 0 , m u l ← 1 add \leftarrow 0, mul \leftarrow 1add←0,mul←1区间修改update若当前节点区间被完全包含直接应用懒标记否则先下传懒标记再递归处理左右子树最后向上更新区间查询query若当前节点区间被完全包含直接返回s u m sumsum否则先下传懒标记再递归查询左右子树并合并结果模数处理所有运算结果对P PP取模防止溢出时间/空间复杂度时间复杂度O ( M log ⁡ N ) O(M \log N)O(MlogN)每次区间修改和查询均为O ( log ⁡ N ) O(\log N)O(logN)M MM次操作总计O ( M log ⁡ N ) O(M \log N)O(MlogN)空间复杂度O ( N ) O(N)O(N)线段树开4 N 4N4N空间存储节点信息线段树懒标记的核心思想延迟下放修改操作不立即更新到每个叶子节点而是记录在对应区间节点上查询时再按需下传将多次修改的复杂度从O ( N ) O(N)O(N)优化到O ( log ⁡ N ) O(\log N)O(logN)标记叠加与优先级当已有懒标记( a d d o l d , m u l o l d ) (add_{old}, mul_{old})(addold​,mulold​)时新操作( a d d n e w , m u l n e w ) (add_{new}, mul_{new})(addnew​,mulnew​)的叠加公式为m u l ← m u l o l d × m u l n e w mul \leftarrow mul_{old} \times mul_{new}mul←mulold​×mulnew​a d d ← a d d o l d × m u l n e w a d d n e w add \leftarrow add_{old} \times mul_{new} add_{new}add←addold​×mulnew​addnew​确保先乘后加的运算顺序完全覆盖剪枝若当前节点区间被操作区间完全包含直接在该节点打标记并停止递归避免不必要的下传适用于区间修改 区间查询类问题尤其是涉及多种操作叠加的场景【算法标签】#线段树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005,INF1e18;// N: 最大数列长度; INF: 无穷大intn,m,p;// n: 数列长度; m: 操作次数; p: 模数intw[N];// w[i]: 数列初始值structNode// 线段树节点结构体{intl,r;// l: 区间左端点; r: 区间右端点intsum,add,mul;// sum: 区间和; add: 加法懒标记; mul: 乘法懒标记}tr[N*4];// 线段树数组开 4 倍空间voidpushup(intu)// 由子节点信息计算父节点信息向上更新{tr[u].sum(tr[u1].sumtr[u1|1].sum)%p;}voideval(Nodet,intadd,intmul)// 对节点 t 应用加法 add 和乘法 mul 的懒标记{t.sum(t.sum*mul(t.r-t.l1)*add)%p;// 更新区间和t.mult.mul*mul%p;// 更新乘法懒标记t.add(t.add*muladd)%p;// 更新加法懒标记先乘后加}voidpushdown(intu)// 将父节点的懒标记下传给子节点{eval(tr[u1],tr[u].add,tr[u].mul);// 下传给左子树eval(tr[u1|1],tr[u].add,tr[u].mul);// 下传给右子树tr[u].add0,tr[u].mul1;// 清空父节点的懒标记}voidbuild(intu,intl,intr)// 建立线段树u: 节点编号[l,r]: 节点区间{if(lr)// 叶子节点tr[u]{l,r,w[r],0,1};// 初始化sum初始值add0mul1else{tr[u]{l,r,0,0,1};// 初始化内部节点intmidlr1;// 计算区间中点build(u1,l,mid);// 递归建立左子树build(u1|1,mid1,r);// 递归建立右子树pushup(u);// 向上更新父节点}}voidupdate(intu,intl,intr,intadd,intmul)// 区间更新[l,r] 加 add 乘 mul{if(tr[u].lltr[u].rr)// 当前节点区间被完全包含{eval(tr[u],add,mul);// 直接对当前节点应用懒标记}else{pushdown(u);// 下传懒标记后再递归intmidtr[u].ltr[u].r1;if(lmid)// 左子树有交集update(u1,l,r,add,mul);if(rmid)// 右子树有交集update(u1|1,l,r,add,mul);pushup(u);// 向上更新父节点}}intquery(intu,intl,intr)// 区间查询[l,r] 的和{if(tr[u].lltr[u].rr)// 当前节点区间被完全包含{returntr[u].sum;// 直接返回区间和}else{pushdown(u);// 下传懒标记intmidtr[u].ltr[u].r1;intsum0;if(lmid)// 左子树有交集sumquery(u1,l,r);if(rmid)// 右子树有交集sum(sumquery(u1|1,l,r))%p;returnsum;}}signedmain(){cinnp;// 读入数列长度和模数for(inti1;in;i)// 读入数列初始值cinw[i];build(1,1,n);// 建立线段树cinm;// 读入操作次数while(m--)// 循环处理 m 次操作{intt,l,r,d;// t: 操作类型; l,r: 区间; d: 操作数值cintlr;if(t1)// 操作 1区间乘法{cind;update(1,l,r,0,d);// add0, muld}elseif(t2)// 操作 2区间加法{cind;update(1,l,r,d,1);// addd, mul1}else// 操作 3区间求和coutquery(1,l,r)endl;}return0;}【运行结果】7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 2 35 8