一、题目
二、解法
第一次过历史线段树的题，写篇题解纪念一下
核心思想就是将标记看作一个操作序列，我们需要额外维护一个序列前缀最大值。
具体来说：我们维护 icv,cv,hcv 表示是否被覆盖\(/\)当前的覆盖标记\(/\)历史覆盖标记最大值；维护 ad,had 表示当前的加法标记\(/\)历史加法标记最大值；维护 mx/hmx 表示区间最大值\(/\)历史区间最大值。
关键之处：考虑如何下传，因为在 \(cover\) 操作的时候我们要清空 \(ad\)，那么我们要先把加法标记先下传，不能先下传覆盖标记是因为这样会直接破坏儿子的加法标记。注意在操作序列出现 \(cover\) 之后，我们就不能直接进行加法操作了，因为这样标记会混乱，但是我们能很容易的把加法操作等价转化成覆盖操作。
总结一句：对于历史问题，想象一个操作序列来思考，要考虑操作之间的互相影响，可以把操作序列“分段”来解决这种影响，比如本题就是以 \(cover\) 操作来分段的（以后的操作就只用 \(cover\)）。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
const int inf = -2147483648;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m;char s[10];
struct tree
{
int icv,hcv,cv,had,ad,mx,hmx;
tree() {icv=hcv=cv=had=ad=0;mx=hmx=inf;}
void cover(int d,int hd)
{
if(icv) hcv=max(hcv,hd);
else hcv=hd,icv=1;
mx=cv=d;
hmx=max(hmx,hd);
ad=0;
}
void Add(int d,int hd)
{
had=max(had,ad+hd);
hmx=max(hmx,mx+hd);
ad+=d;mx+=d;
}
void add(int d,int hd)
{
if(icv) cover(cv+d,cv+hd);
else Add(d,hd);
}
}tr[4*M];
void down(int i)
{
//download the add tag
tr[i<<1].add(tr[i].ad,tr[i].had);
tr[i<<1|1].add(tr[i].ad,tr[i].had);
tr[i].ad=tr[i].had=0;
//download the covering tag
if(tr[i].icv)
{
tr[i<<1].cover(tr[i].cv,tr[i].hcv);
tr[i<<1|1].cover(tr[i].cv,tr[i].hcv);
tr[i].icv=tr[i].hcv=tr[i].cv=0;
}
}
void up(int i)
{
tr[i].mx=max(tr[i<<1].mx,tr[i<<1|1].mx);
tr[i].hmx=max(tr[i].hmx,tr[i].mx);
}
void cov(int i,int l,int r,int L,int R,int x)
{
if(l>R || L>r) return ;
if(L<=l && r<=R)
{
tr[i].cover(x,x);
return ;
}
int mid=(l+r)>>1;down(i);
cov(i<<1,l,mid,L,R,x);
cov(i<<1|1,mid+1,r,L,R,x);
up(i);
}
void add(int i,int l,int r,int L,int R,int x)
{
if(l>R || L>r) return ;
if(L<=l && r<=R)
{
tr[i].add(x,x);
return ;
}
int mid=(l+r)>>1;down(i);
add(i<<1,l,mid,L,R,x);
add(i<<1|1,mid+1,r,L,R,x);
up(i);
}
int ask(int i,int l,int r,int L,int R)
{
if(L>r || l>R) return inf;
if(L<=l && r<=R) return tr[i].mx;
int mid=(l+r)>>1;down(i);
return max(ask(i<<1,l,mid,L,R),
ask(i<<1|1,mid+1,r,L,R));
}
int hask(int i,int l,int r,int L,int R)
{
if(L>r || l>R) return inf;
if(L<=l && r<=R) return tr[i].hmx;
int mid=(l+r)>>1;down(i);
return max(hask(i<<1,l,mid,L,R),
hask(i<<1|1,mid+1,r,L,R));
}
void build(int i,int l,int r)
{
if(l==r)
{
tr[i].mx=tr[i].hmx=read();
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
up(i);
}
signed main()
{
n=read();build(1,1,n);
m=read();
while(m--)
{
scanf("%s",s);int l=read(),r=read();
if(s[0]=='Q') printf("%d\n",ask(1,1,n,l,r));
if(s[0]=='A') printf("%d\n",hask(1,1,n,l,r));
if(s[0]=='P') add(1,1,n,l,r,read());
if(s[0]=='C') cov(1,1,n,l,r,read());
}
}