企业官网建设流程全解析

P1253 扶苏的问题

网页链接

P1253 扶苏的问题

题目描述

给定一个长度为n nn的序列a aa，要求支持如下三个操作：

1. 给定区间[ l , r ] [l, r][l,r]，将区间内每个数都修改为x xx。
2. 给定区间[ l , r ] [l, r][l,r]，将区间内每个数都加上x xx。
3. 给定区间[ l , r ] [l, r][l,r]，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度n nn和操作的个数q qq。
第二行有n nn个整数，第i ii个整数表示序列中的第i ii个数a i a_iai​。
接下来q qq行，每行表示一个操作。每行首先有一个整数o p opop，表示操作的类型。

• 若o p = 1 op = 1op=1，则接下来有三个整数l , r , x l, r, xl,r,x，表示将区间[ l , r ] [l, r][l,r]内的每个数都修改为x xx。
• 若o p = 2 op = 2op=2，则接下来有三个整数l , r , x l, r, xl,r,x，表示将区间[ l , r ] [l, r][l,r]内的每个数都加上x xx。
• 若o p = 3 op = 3op=3，则接下来有两个整数l , r l, rl,r，表示查询区间[ l , r ] [l, r][l,r]内的最大值。

输出格式

对于每个o p = 3 op = 3op=3的操作，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

6 6 1 1 4 5 1 4 1 1 2 6 2 3 4 2 3 1 4 3 2 3 1 1 6 -1 3 1 6

输出 #1

7 6 -1

输入输出样例 #2

输入 #2

4 4 10 4 -3 -7 1 1 3 0 2 3 4 -4 1 2 4 -9 3 1 4

输出 #2

0

说明/提示

数据规模与约定

• 对于10 % 10\%10%的数据，n = q = 1 n = q = 1n=q=1。
• 对于40 % 40\%40%的数据，n , q ≤ 10 3 n, q \leq 10^3n,q≤103。
• 对于50 % 50\%50%的数据，0 ≤ a i , x ≤ 10 4 0 \leq a_i, x \leq 10^40≤ai​,x≤104。
• 对于60 % 60\%60%的数据，o p ≠ 1 op \neq 1op=1。
• 对于90 % 90\%90%的数据，n , q ≤ 10 5 n, q \leq 10^5n,q≤105。
• 对于100 % 100\%100%的数据，1 ≤ n , q ≤ 10 6 1 \leq n, q \leq 10^61≤n,q≤106，1 ≤ l , r ≤ n 1 \leq l, r \leq n1≤l,r≤n，o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\}op∈{1,2,3}，∣ a i ∣ , ∣ x ∣ ≤ 10 9 |a_i|, |x| \leq 10^9∣ai​∣,∣x∣≤109。

提示

请注意大量数据读入对程序效率造成的影响。

解题思路

本题是**线段树（区间赋值、区间加、区间最大值查询）**的经典模板题。需要支持三种操作：区间赋值、区间加、区间求最大值。由于操作可能混合出现，且赋值会覆盖之前的加法，因此在线段树中需要维护两个懒标记：赋值标记和加法标记，并明确规定它们的优先级。

1. 问题等价转化

• 给定长度为n nn的序列a aa，支持q qq次操作：
  • op=1：将区间[ l , r ] [l, r][l,r]内所有数修改为x xx。
  • op=2：将区间[ l , r ] [l, r][l,r]内所有数加上x xx。
  • op=3：查询区间[ l , r ] [l, r][l,r]内的最大值。
• 直接暴力修改和查询复杂度为O ( n q ) O(nq)O(nq)，无法通过n , q ≤ 10 6 n, q \le 10^6n,q≤106的数据规模。因此采用线段树，将每次操作降到O ( log ⁡ n ) O(\log n)O(logn)。

2. 线段树节点设计与懒标记

• 每个节点维护：
  • w：该区间内的最大值。
  • t1：赋值懒标记。若存在赋值标记，则t1存储赋的值；否则用一个特殊值（如1e18）表示无赋值标记。
  • t2：加法懒标记。表示在赋值标记之后（或没有赋值标记时）需要加上的值。
• 标记优先级：赋值标记会覆盖之前的所有操作（包括加法和赋值），因此当对一个节点执行赋值操作时，直接更新w和t1，并将t2清零。当执行加法操作时：
  • 若当前节点有赋值标记（t1 != nul），则直接将t1 += x，并更新w += x。
  • 否则，将t2 += x，并更新w += x。
• 下传标记（pushdown）：
  • 若存在赋值标记，则先将赋值标记下传给左右儿子（覆盖它们的值），并清除当前赋值标记。
  • 否则若存在加法标记，则将加法标记下传给左右儿子，并清除当前加法标记。
• 合并（pushup）：w = max(左儿子.w, 右儿子.w)。

3. 算法实现

代码采用动态分配节点的线段树（使用静态数组池模拟）。核心操作：

• 建树：递归构建，叶子节点w = a[l]，内部节点w = max(ls->w, rs->w)。初始化t1 = nul，t2 = 0。
• 区间更新upd(L, R, x, op)：
  • 若当前节点区间完全包含于[L, R]，则根据op调用mkt1(x)（赋值）或mkt2(x)（加法），直接修改w和懒标记。
  • 否则，若区间有交集，先pd()下传标记，再递归更新左右子树，最后pu()更新当前节点的w。
• 区间查询qry(L, R)：
  • 若完全包含，返回w。
  • 否则，若区间有交集，先pd()下传标记，再返回左右子树查询结果的最大值。
  • 无交集返回极小值（如-nul）。

4. 复杂度分析

• 时间复杂度：建树O ( n ) O(n)O(n)。每次操作（更新或查询）最多访问O ( log ⁡ n ) O(\log n)O(logn)个节点，每个节点操作常数时间。总时间复杂度O ( ( n + q ) log ⁡ n ) O((n + q) \log n)O((n+q)logn)。n , q ≤ 10 6 n, q \le 10^6n,q≤106，在 1 秒内配合快速 I/O 可以完成。
• 空间复杂度：线段树节点数约为4 n 4n4n，使用静态数组池分配，空间O ( n ) O(n)O(n)，满足 256M 限制。

总结

通过维护赋值和加法两个懒标记，并明确规定“赋值覆盖加法”的优先级，可以高效处理混合的区间修改操作。线段树的每个节点维护区间最大值，支持O ( log ⁡ n ) O(\log n)O(logn)的更新和查询。实现时注意懒标记的下传顺序和特殊值的处理。

代码简要说明

• 结构体Node：包含区间左右端点l, r，最大值w，赋值标记t1，加法标记t2，左右儿子指针。
  • mkt1(x)：执行赋值操作，设置w = t1 = x，t2 = 0。
  • mkt2(x)：执行加法操作，w += x；若已有赋值标记则t1 += x，否则t2 += x。
  • pd()：下传标记，优先处理赋值标记，再处理加法标记。
  • pu()：用左右儿子的最大值更新当前节点的w。
  • upd(L, R, x, op)：区间更新，根据op选择赋值或加法。
  • qry(L, R)：区间查询最大值。
• New(L, R)：递归建树，从数组a读取叶子值。
• 主函数：读入n , q n, qn,q和数组，建树，循环处理操作。使用cin并关闭同步加速 I/O。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1000006;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll nul=1e18;ll n,q;ll a[N];structNode{ll l,r;ll w,t1,t2;Node*ls,*rs;voidmkt1(ll x){w=t1=x;t2=0;}voidmkt2(ll x){w+=x;if(t1!=nul)t1+=x;elset2+=x;}voidpd(){if(t1!=nul){ls->mkt1(t1);rs->mkt1(t1);t1=nul;}elseif(t2){ls->mkt2(t2);rs->mkt2(t2);t2=0;}}voidpu(){w=max(ls->w,rs->w);}boolir(ll L,ll R){returnL<=l&&r<=R;}booloor(ll L,ll R){returnl>R||r<L;}voidupd(ll L,ll R,ll x,ll op){if(ir(L,R)){if(op==1)mkt1(x);elsemkt2(x);}elseif(!oor(L,R)){pd();ls->upd(L,R,x,op);rs->upd(L,R,x,op);pu();}}llqry(ll L,ll R){if(ir(L,R))returnw;elseif(!oor(L,R)){pd();returnmax(ls->qry(L,R),rs->qry(L,R));}elsereturn-nul;}};Node Mem[N<<1],*pool=Mem;Node*New(ll L,ll R){autou=pool++;u->l=L;u->r=R;u->t1=nul;u->t2=0;if(L!=R){ll M=(L+R)>>1;u->ls=New(L,M);u->rs=New(M+1,R);u->pu();}elseu->w=a[L];returnu;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>q;for(ll i=1;i<=n;i++)cin>>a[i];autorot=New(1,n);for(ll op,l,r,x;q;q--){cin>>op>>l>>r;if(op!=3){cin>>x;rot->upd(l,r,x,op);}elsecout<<rot->qry(l,r)<<'\n';}return0;}