题解：AcWing 1277 维护序列

【题目来源】

AcWing：1277. 维护序列 - AcWing题库

【题目描述】

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为N NN的数列，不妨设为a 1 , a 2 , … , a N a_1,a_2,…,a_Na1​,a2​,…,aN​。

有如下三种操作形式：

1. 把数列中的一段数全部乘一个值；
2. 把数列中的一段数全部加一个值；
3. 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模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 11：1 t g c，表示把所有满足t ≤ i ≤ g t≤i≤gt≤i≤g的a i a_iai​改为a i × c a_i×cai​×c；
• 操作2 22：2 t g c，表示把所有满足t ≤ i ≤ g t≤i≤gt≤i≤g的a i a_iai​改为a i + c a_i+cai​+c；
• 操作3 33：3 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

【核心思想】

1. 问题分析：给定长度为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）**问题，核心挑战在于两种修改操作的叠加与优先级处理。

2. 算法选择：

   • 线段树（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，处理"先乘后加"的复合操作

3. 关键步骤：

   • 建树：递归构建线段树，每个节点存储区间[ l , r ] [l, r][l,r]、区间和s u m sumsum、加法懒标记a d d = 0 add = 0add=0、乘法懒标记m u l = 1 mul = 1mul=1
   • 懒标记应用（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−l+1)×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取模，防止溢出

4. 时间/空间复杂度：

   • 时间复杂度：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空间存储节点信息

5. 线段树懒标记的核心思想：

   • 延迟下放：修改操作不立即更新到每个叶子节点，而是记录在对应区间节点上，查询时再按需下传，将多次修改的复杂度从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​，确保"先乘后加"的运算顺序
   • 完全覆盖剪枝：若当前节点区间被操作区间完全包含，直接在该节点打标记并停止递归，避免不必要的下传
   • 适用于区间修改 + 区间查询类问题，尤其是涉及多种操作叠加的场景

【算法标签】

#线段树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005,INF=1e18;// 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[u<<1].sum+tr[u<<1|1].sum)%p;}voideval(Node&t,intadd,intmul)// 对节点 t 应用加法 add 和乘法 mul 的懒标记{t.sum=(t.sum*mul+(t.r-t.l+1)*add)%p;// 更新区间和t.mul=t.mul*mul%p;// 更新乘法懒标记t.add=(t.add*mul+add)%p;// 更新加法懒标记（先乘后加）}voidpushdown(intu)// 将父节点的懒标记下传给子节点{eval(tr[u<<1],tr[u].add,tr[u].mul);// 下传给左子树eval(tr[u<<1|1],tr[u].add,tr[u].mul);// 下传给右子树tr[u].add=0,tr[u].mul=1;// 清空父节点的懒标记}voidbuild(intu,intl,intr)// 建立线段树，u: 节点编号，[l,r]: 节点区间{if(l==r)// 叶子节点tr[u]={l,r,w[r],0,1};// 初始化：sum=初始值，add=0，mul=1else{tr[u]={l,r,0,0,1};// 初始化内部节点intmid=l+r>>1;// 计算区间中点build(u<<1,l,mid);// 递归建立左子树build(u<<1|1,mid+1,r);// 递归建立右子树pushup(u);// 向上更新父节点}}voidupdate(intu,intl,intr,intadd,intmul)// 区间更新，[l,r] 加 add 乘 mul{if(tr[u].l>=l&&tr[u].r<=r)// 当前节点区间被完全包含{eval(tr[u],add,mul);// 直接对当前节点应用懒标记}else{pushdown(u);// 下传懒标记后再递归intmid=tr[u].l+tr[u].r>>1;if(l<=mid)// 左子树有交集update(u<<1,l,r,add,mul);if(r>mid)// 右子树有交集update(u<<1|1,l,r,add,mul);pushup(u);// 向上更新父节点}}intquery(intu,intl,intr)// 区间查询，[l,r] 的和{if(tr[u].l>=l&&tr[u].r<=r)// 当前节点区间被完全包含{returntr[u].sum;// 直接返回区间和}else{pushdown(u);// 下传懒标记intmid=tr[u].l+tr[u].r>>1;intsum=0;if(l<=mid)// 左子树有交集sum=query(u<<1,l,r);if(r>mid)// 右子树有交集sum=(sum+query(u<<1|1,l,r))%p;returnsum;}}signedmain(){cin>>n>>p;// 读入数列长度和模数for(inti=1;i<=n;i++)// 读入数列初始值cin>>w[i];build(1,1,n);// 建立线段树cin>>m;// 读入操作次数while(m--)// 循环处理 m 次操作{intt,l,r,d;// t: 操作类型; l,r: 区间; d: 操作数值cin>>t>>l>>r;if(t==1)// 操作 1：区间乘法{cin>>d;update(1,l,r,0,d);// add=0, mul=d}elseif(t==2)// 操作 2：区间加法{cin>>d;update(1,l,r,d,1);// add=d, mul=1}else// 操作 3：区间求和cout<<query(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