思路：
线段树专题讲的。以下为讲课时的课件：
给出序列，要求查询一些区间的最大值、历史最大值，支持区间加、区间修改。序列长度和操作数<=1e5。
维护标记的线段树裸题。出这道题的目的就是为了让大家加强对于线段树标记下传的理解，以及线段树维护信息时分类讨论一定要明确。
在确定了要写线段树后，先考虑要维护哪些标记。然后思考这些标记应当如何维护，何时下传，何时修改。特别注意，当区间加、区间覆盖操作同时存在时，标记之间的先后处理顺序非常重要。
这道题细节非常多，难点集中于标记下传。
具体做法：对于既有set又有add的线段树，在任何时刻，同一个节点上必然不能同时出现set和add两种标记，因为set和add会由顺序不同导致冲突。
· 我们维护六个信息：
· mx[o]表示o点当前最大值；
· gmx[o]表示o点全局最大值；
· add[o]表示o点当前增加的值；
· gadd[o]表示o点从上一次pushdown后直到现在，出现的最大add值；
· set[o]表示o点当前赋的值；
· gset[o]表示o点从上一次pushdown后直到现在，出现的最大set值。
· ※对于不存在set值的节点，均赋为-inf。
接着，先不管查询历史操作，只考虑标记的合并与传递。既然两种标记不能并存，那在传递的时候一定要讨论当前节点和子节点的标记情况，分情况传递。
· 1.父节点有add，子节点有add：直接将父节点的add累加到子节点上。
· 2.父节点有add，子节点有set：将父节点的add值累加到子节点的set值上。
· 3.父节点有set：无论子节点的情况，直接覆盖子节点的set值，同时清掉子节点的add值。
这样，每次访问到一个非叶子节点时，首先进行标记下传更新子节点信息，清空当前节点标记，而每次修改时，如果区间被完全包含，则直接给节点打上标记，更新当前节点信息即可。
最后来考虑历史信息的维护。我们需要在进行操作时，不遗漏没有进行操作的节点出现的最大值，所以维护了“从上次pushdown该节点直到现在，区间中出现的最大set与add标记”，这样，区间的历史最值（答案、set、add）就可能来自于父节点没有pushdown的最大set或者add，在pushdown父节点的时候考虑就好了。另外，在完成对子节点set、add标记更新之后还要再考虑对子节点历史标记的影响。这样，即可保证访问到的节点的信息
都是最新的。
· 你会写到自闭的。
· 就算是看标程也要自己写一遍。
· 做维护信息比较复杂的线段树题目时，一定要找对维护标记的时机，清晰而彻底的认真思考会不会有遗漏，可以避免长时间的盲目调试。
果然写自闭了...
最后差不多是对着题解看上几遍然后抄的。
最初容易把问题想简单，以为只要随便用个gmax表示历史最大值，然后就能直接维护了。
实际上，考虑这种情况：我们对一段区间曾做过一些操作，标记停留在某层还没有被下放。之后又进行一项新的操作，把原有的标记覆盖掉了，于是在维护子节点的gmax值时就会出错。
那么该怎么做呢？
为了防止信息丢失，必须保证每次pushdown之前，还没有被下放的标记能够更新子节点的gmax，然后才能把这个标记覆盖掉。
如果每次pushdown都先把原来标记下放一遍，复杂度会退化->TLE.
我们可以维护“从上次pushdown到现在为止没有被下放的最大add值和set值”，问题就解决了。
以上是基本思想，只涉及线段树最基本的lazytag，但具体实现需要对lazy标记的下放有深刻的理解。
题目中有两个操作：add和set，我们考虑下放顺序，共四种情况：
- add - add
- set - set
- set - add
- add - set
前两种直接维护，第三种可以把add累加到set上。
于是能做了，有的题解就是直接分两类讨论：add-add，add-set。
这里我们也可以按讲课时的方法，用set盖掉add，于是任意时刻线段树节点上只会出现一种标记。可以在提交的代码中加入断言进行验证。
注意区分：
mx、add、set标记只会在Add操作、Set操作、pushdown时父节点的add和set标记时更新，gmax、gadd、gset在各种操作时都可能被更新。
把不同的更新分别写成函数，可以帮助整理思维。
Code：
#include <bits/stdc .h>
using namespace std;
const int N=1e6,inf=0x3f3f3f3f;
int n,T,ans_max,ans_gmax;
struct Tree{
int l,r,mx,gmx,add,gadd,set,gset;
#define l(p) (node[p].l)
#define r(p) (node[p].r)
#define mx(p) (node[p].mx)
#define gmx(p) (node[p].gmx)
#define add(p) (node[p].add)
#define gadd(p) (node[p].gadd)
#define set(p) (node[p].set)
#define gset(p) (node[p].gset)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l(p) r(p))>>1)
}node[N<<2];
inline void cmax(int &a,int b){ a=((b>a)?b:a); }
void pup(int p){
mx(p)=max(mx(ls(p)),mx(rs(p)));
cmax(gmx(p),max(gmx(ls(p)),gmx(rs(p))));
}
void build(int p,int l,int r){
l(p)=l;r(p)=r;
set(p)=gset(p)=-inf;
if(l==r){
scanf("%lld",&mx(p));
gmx(p)=mx(p);
return;
}
build(ls(p),l,mid);
build(rs(p),mid 1,r);
pup(p);
}
void m_add(int p,int val){/*p节点实际增加val*/
cmax(gmx(p),mx(p) =val);
if(set(p)!=-inf) cmax(gset(p),set(p) =val);
else cmax(gadd(p),add(p) =val);
}
void m_set(int p,int val){/*p节点实际被val覆盖*/
cmax(gmx(p),mx(p)=val);
cmax(gset(p),set(p)=val);
add(p)=0;
}
void g_add(int p,int val){/*用父亲的gadd更新p节点*/
cmax(gmx(p),mx(p) val);
if(set(p)!=-inf) cmax(gset(p),set(p) val);
else cmax(gadd(p),add(p) val);
}
void g_set(int p,int val){/*用父亲的gset更新p节点*/
cmax(gmx(p),val);
cmax(gset(p),val);
}
void pdown(int p){
if(gadd(p)){
g_add(ls(p),gadd(p));
g_add(rs(p),gadd(p));
gadd(p)=0;
}
if(gset(p)!=-inf){
g_set(ls(p),gset(p));
g_set(rs(p),gset(p));
gset(p)=-inf;
}
if(add(p)){
m_add(ls(p),add(p));
m_add(rs(p),add(p));
add(p)=0;
}
if(set(p)!=-inf){
m_set(ls(p),set(p));
m_set(rs(p),set(p));
set(p)=-inf;
}
}
void Add(int p,int L,int R,int val){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) return m_add(p,val);
pdown(p);
Add(ls(p),L,R,val);
Add(rs(p),L,R,val);
pup(p);
}
void Set(int p,int L,int R,int val){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) return m_set(p,val);
pdown(p);
Set(ls(p),L,R,val);
Set(rs(p),L,R,val);
pup(p);
}
void query(int p,int L,int R){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) {
ans_max=max(ans_max,mx(p));
ans_gmax=max(ans_gmax,gmx(p));
return;
}
pdown(p);
query(ls(p),L,R);
query(rs(p),L,R);
}
int main(){
scanf("%d",&n);
build(1,1,n);
scanf("%d",&T);
char op[5];
int x,y,z;
while(T--){
ans_max=ans_gmax=-inf;
scanf("%s",op);
if(op[0]=='Q') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_max);
} else if(op[0]=='A') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_gmax);
} else if(op[0]=='P') {
scanf("%d%d%d",&x,&y,&z);
Add(1,x,y,z);
} else if(op[0]=='C') {
scanf("%d%d%d",&x,&y,&z);
Set(1,x,y,z);
}
}
return 0;
}
来源：https://www./content-4-356951.html
|
