Tyvj 1518 CPU监控——极恶线段树
枫林晚
2018-05-05 18:00:35
题目大意：
给定一个区间及其各个元素的初值，要求支持如下操作：
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水过。
详见代码：
```cpp
#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\n",qx(root,1,n,x,y));
}
else if(q=='A')
{
scanf("%d%d",&x,&y);
printf("%lld\n",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;
}
```