http://www.lydsy.com/JudgeOnline/problem.php?id=3064 (题目链接)
题意
给出一个长度为$n$的数列$A$，同时定义一个辅助数组$B$，$B$开始与$A$完全相同。接下来进行$m$次操作， 有4种类型：
- 区间加法
- 区间覆盖
- 查询$A$的区间最值
- 查询$B$的区间最值
Solution
参考吉利论文。
最恶心的就是覆盖标记和加减标记的合并= =，一定要想清楚所有情况。
细节
代码略丑= =
代码
// bzoj3938
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<30)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=100010;
int n,m,a[maxn];
char ch[100];
struct node {int l,r,nadd,padd,ncov,pcov,nmx,pmx;}tr[maxn<<2]; void pushup(int k) {
tr[k].nmx=max(tr[k<<1].nmx,tr[k<<1|1].nmx);
tr[k].pmx=max(tr[k<<1].pmx,tr[k<<1|1].pmx);
}
void pushdown(int k) {
for (int x,i=0;x=k<<1|i,i<2;i++) {
tr[x].pmx=max(tr[x].pmx,max(tr[k].padd+tr[x].nmx,tr[k].pcov));
if (tr[k].ncov==-inf) {
tr[x].nmx+=tr[k].nadd;
if (tr[x].ncov==-inf) tr[x].padd=max(tr[x].padd,tr[x].nadd+tr[k].padd),tr[x].nadd+=tr[k].nadd;
else tr[x].pcov=max(tr[x].pcov,tr[x].ncov+tr[k].padd),tr[x].ncov=tr[x].nmx;
}
else {
if (tr[x].ncov==-inf) tr[x].padd=max(tr[x].padd,tr[x].nadd+tr[k].padd);
else tr[x].pcov=max(tr[x].pcov,tr[x].nmx+tr[k].padd);
tr[x].nmx=tr[x].ncov=tr[k].ncov,tr[x].pcov=max(tr[x].pcov,tr[k].pcov);
}
}
tr[k].ncov=tr[k].pcov=-inf;tr[k].nadd=tr[k].padd=0;
}
void build(int k,int s,int t) {
tr[k].l=s;tr[k].r=t;
tr[k].ncov=tr[k].pcov=-inf;
if (s==t) {tr[k].nmx=tr[k].pmx=a[s];return;}
int mid=(s+t)>>1;
build(k<<1,s,mid);
build(k<<1|1,mid+1,t);
pushup(k);
}
int query(int k,int s,int t,int op) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==s && r==t) return op ? tr[k].pmx : tr[k].nmx;
pushdown(k);
if (t<=mid) return query(k<<1,s,t,op);
else if (s>mid) return query(k<<1|1,s,t,op);
else return max(query(k<<1,s,mid,op),query(k<<1|1,mid+1,t,op));
}
void modify(int k,int s,int t,int val,int op) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==s && r==t) {
if (op) {
tr[k].pmx=max(tr[k].pmx,tr[k].nmx=val);
tr[k].pcov=max(tr[k].pcov,tr[k].ncov=val);
}
else {
tr[k].pmx=max(tr[k].pmx,tr[k].nmx+=val);
if (tr[k].ncov==-inf) tr[k].padd=max(tr[k].padd,tr[k].nadd+=val);
else tr[k].pcov=max(tr[k].pcov,tr[k].ncov=tr[k].nmx);
}
return;
}
pushdown(k);
if (t<=mid) modify(k<<1,s,t,val,op);
else if (s>mid) modify(k<<1|1,s,t,val,op);
else modify(k<<1,s,mid,val,op),modify(k<<1|1,mid+1,t,val,op);
pushup(k);
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
for (int x,y,z,i=1;i<=m;i++) {
scanf("%s%d%d",ch,&x,&y);
if (ch[0]=='Q') printf("%d\n",query(1,x,y,0));
if (ch[0]=='A') printf("%d\n",query(1,x,y,1));
if (ch[0]=='P') scanf("%d",&z),modify(1,x,y,z,0);
if (ch[0]=='C') scanf("%d",&z),modify(1,x,y,z,1);
}
return 0;
}