题目大意：
给定一个区间及其各个元素的初值，要求支持如下操作：
1.区间加
2.区间赋值
3.查询区间最大值
4.查询区间历史最大值
分析：
容易想到线段树，但是细思恶极（仔细想想恶心到了极点）的是，最后查询区间历史最大值的操作。
如果只记录区间历史最大值显然不能下放，如果单纯更新区间加，区间赋值最大值，可能会出现历史最大值更新不及时的情况。如先赋值很大值，未来得及下放，又赋值很小，导致子区间历史最大值不能更新。又如如果区间加只取最大值，可能会只取最大值，导致实际上忽视了一些使区间加变小的操作。
。。。。（此处省略若千字）
所以我们记录如下几点：
1.mx(x)当前区间最大值
2.hx(x)历史区间最大值
3.ad(x)当前区间加
4.ha(x)历史最大区间加
5.ch(x)当前区间赋值
6.hc(x)历史最大区间赋值
注意 ：
这里我们所谓的ha,hc是指在上一次pushdown之后，期间进行的操作中的最大值。是可以清零的，不像hx。
初值：ha=ad=0,ch=hc=-inf。
因为每次都先进行pushdown，所以ha、hc直接随着ad、ch更新。
注意的是pushdown中的许多讨论，自己分析清楚。
其实每次都pushdown是很慢的，会tle两个点。
然后就把区间内的l、r不记录了，竟然不开O2水过。
详见代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=100000+10; const ll inf=1e13; int root,n,e; ll a[N]; int cc; struct node{ ll add,ch; ll mx,hx; ll had,hch;//一段时间内最值 #define ad(x) t[x].add #define ch(x) t[x].ch #define mx(x) t[x].mx #define hx(x) t[x].hx #define ha(x) t[x].had #define hc(x) t[x].hch #define l(x) t[x].l #define r(x) t[x].r }t[4*N]; void pushup(int x) { int s1=x<<1,s2=x<<1|1; mx(x)=max(mx(s1),mx(s2)); hx(x)=max(hx(s1),hx(s2)); } void build(int x,int L,int R) { if(L==R) { ad(x)=0;ch(x)=-inf;ha(x)=0;hc(x)=-inf; mx(x)=hx(x)=a[L]; return; } int mid=(L+R)>>1; ad(x)=0;ch(x)=-inf;ha(x)=0;hc(x)=-inf; mx(x)=hx(x)=-inf; build(x<<1,L,mid); build(x<<1|1,mid+1,R); pushup(x); } void pushdown(int x) { for(int i=0;i<=1;i++) { int s=x<<1|i; hx(s)=max(hx(s),max(mx(s)+ha(x),hc(x))); if(ch(s)!=-inf) hc(s)=max(hc(s),ch(s)+ha(x)); else ha(s)=max(ha(s),ad(s)+ha(x)); if(ad(x)) { if(ch(s)!=-inf) ch(s)+=ad(x); else ad(s)+=ad(x); mx(s)+=ad(x); } if(ch(x)!=-inf) { mx(s)=ch(s)=ch(x); ad(s)=0; } hc(s)=max(hc(s),max(ch(s),hc(x))); ha(s)=max(ha(s),ad(s)); } hc(x)=-inf; ad(x)=0;ch(x)=-inf;ha(x)=0; } void add(int x,int l,int r,int L,int R,ll c) { if(l!=r)pushdown(x); if(L<=l&&r<=R) { ad(x)+=c;ha(x)+=c; mx(x)+=c;hx(x)=max(mx(x),hx(x)); return; } int mid=(l+r)>>1; if(L<=mid) add(x<<1,l,mid,L,R,c); if(R>mid) add(x<<1|1,mid+1,r,L,R,c); pushup(x); } void chan(int x,int l,int r,int L,int R,ll c) { if(l!=r)pushdown(x); if(L<=l&&r<=R) { ch(x)=c,mx(x)=c;hc(x)=c; hx(x)=max(hx(x),mx(x)); return; } int mid=(l+r)>>1; if(L<=mid) chan(x<<1,l,mid,L,R,c); if(R>mid) chan(x<<1|1,mid+1,r,L,R,c); pushup(x); } ll qx(int x,int l,int r,int L,int R) { if(l!=r)pushdown(x); if(L<=l&&r<=R) { return mx(x); } int mid=(l+r)>>1; ll res=-inf; if(L<=mid) res=max(res,qx(x<<1,l,mid,L,R)); if(R>mid) res=max(res,qx(x<<1|1,mid+1,r,L,R)); return res; } ll qh(int x,int l,int r,int L,int R) { if(l!=r)pushdown(x); if(L<=l&&r<=R) { return hx(x); } int mid=(l+r)>>1; ll res=-inf; if(L<=mid) res=max(res,qh(x<<1,l,mid,L,R)); if(R>mid) res=max(res,qh(x<<1|1,mid+1,r,L,R)); return res; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); root=1; build(1,1,n); scanf("%d",&e); char q; int x,y; ll z; while(e) { cin>>q; if(q=='Q') { scanf("%d%d",&x,&y); printf("%lld ",qx(root,1,n,x,y)); } else if(q=='A') { scanf("%d%d",&x,&y); printf("%lld ",qh(root,1,n,x,y)); } else if(q=='P') { scanf("%d%d%lld",&x,&y,&z); add(root,1,n,x,y,z); } else{ scanf("%d%d%lld",&x,&y,&z); chan(root,1,n,x,y,z); } e--; } return 0; }
做这个题要有勇于试错的精神，和坚持不懈的意志。