P1253 扶苏的问题网页链接P1253 扶苏的问题题目描述给定一个长度为n nn的序列a aa要求支持如下三个操作给定区间[ l , r ] [l, r][l,r]将区间内每个数都修改为x xx。给定区间[ l , r ] [l, r][l,r]将区间内每个数都加上x xx。给定区间[ 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 1op1则接下来有三个整数l , r , x l, r, xl,r,x表示将区间[ l , r ] [l, r][l,r]内的每个数都修改为x xx。若o p 2 op 2op2则接下来有三个整数l , r , x l, r, xl,r,x表示将区间[ l , r ] [l, r][l,r]内的每个数都加上x xx。若o p 3 op 3op3则接下来有两个整数l , r l, rl,r表示查询区间[ l , r ] [l, r][l,r]内的最大值。输出格式对于每个o p 3 op 3op3的操作输出一行一个整数表示答案。输入输出样例 #1输入 #16 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输出 #17 6 -1输入输出样例 #2输入 #24 4 10 4 -3 -7 1 1 3 0 2 3 4 -4 1 2 4 -9 3 1 4输出 #20说明/提示数据规模与约定对于10 % 10\%10%的数据n q 1 n q 1nq1。对于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≤1061 ≤ l , r ≤ n 1 \leq l, r \leq n1≤l,r≤no 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次操作op1将区间[ l , r ] [l, r][l,r]内所有数修改为x xx。op2将区间[ l , r ] [l, r][l,r]内所有数加上x xx。op3查询区间[ 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若存在赋值标记则先将赋值标记下传给左右儿子覆盖它们的值并清除当前赋值标记。否则若存在加法标记则将加法标记下传给左右儿子并清除当前加法标记。合并pushupw max(左儿子.w, 右儿子.w)。3. 算法实现代码采用动态分配节点的线段树使用静态数组池模拟。核心操作建树递归构建叶子节点w a[l]内部节点w max(ls-w, rs-w)。初始化t1 nult2 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((nq)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 xt2 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。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1000006;constll INF1e18;constll M1e610;constll mod1e97;ll nul1e18;ll n,q;ll a[N];structNode{ll l,r;ll w,t1,t2;Node*ls,*rs;voidmkt1(ll x){wt1x;t20;}voidmkt2(ll x){wx;if(t1!nul)t1x;elset2x;}voidpd(){if(t1!nul){ls-mkt1(t1);rs-mkt1(t1);t1nul;}elseif(t2){ls-mkt2(t2);rs-mkt2(t2);t20;}}voidpu(){wmax(ls-w,rs-w);}boolir(ll L,ll R){returnLlrR;}booloor(ll L,ll R){returnlR||rL;}voidupd(ll L,ll R,ll x,ll op){if(ir(L,R)){if(op1)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[N1],*poolMem;Node*New(ll L,ll R){autoupool;u-lL;u-rR;u-t1nul;u-t20;if(L!R){ll M(LR)1;u-lsNew(L,M);u-rsNew(M1,R);u-pu();}elseu-wa[L];returnu;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnq;for(ll i1;in;i)cina[i];autorotNew(1,n);for(ll op,l,r,x;q;q--){cinoplr;if(op!3){cinx;rot-upd(l,r,x,op);}elsecoutrot-qry(l,r)\n;}return0;}