( ext{First floor!})
问题
区间加法,区间赋值,询问区间 (max) 以及历史 (max)。
解法
首先有一些定义:
-
add
当前加法标记。 -
hadd
历史最大加法标记。假设某节点的加法标记序列为 (s),那么它就是 (s) 的前缀和的最大值。 -
cov
当前覆盖标记。 -
hcov
历史最大覆盖标记。 -
tag
当前是否覆盖标记。 -
mx
当前区间最大值。 -
h
历史区间最大值。
只有加法操作可以这样维护:
void Add(int d,int hd) {
// d:修改的当前加法标记,hd:修改的历史最大加法标记
hadd=max(hadd,add+hd);
h=max(h,mx+hd);
add+=d,mx+=d;
}
hadd
的更新相当于将两个操作序列接在一起(假设 (a) 在 (b) 之前),那么要么选取 (a) 的 hadd
,要么选取 (a) 的操作和加上 (b) 的 hadd
。
如果又有赋值,又有加法,操作就变得混乱起来。不过,我们可以将一个节点上的操作序列合并成 "加法" + "赋值"。因为赋值之后的加法操作其实也是赋值。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <iostream>
using namespace std;
const int maxn=1e5+5,inf=0x7fffffff;
int n;
char op[5];
struct node {
int mx,h,add,cov,hadd,hcov;
bool tag;
void Cover(int d,int hd) {
if(tag) {
hcov=max(hcov,hd);
}
else {
tag=1;
hcov=hd;
}
add=0;
h=max(h,hd);
cov=mx=d;
}
void Add(int d,int hd) {
hadd=max(hadd,add+hd);
h=max(h,mx+hd);
add+=d,mx+=d;
}
void Change(int d,int hd) {
// 将加法转化成赋值标记
if(tag) Cover(d+cov,hd+cov);
else Add(d,hd);
}
} t[maxn<<2];
void pushUp(int o) {
t[o].mx=max(t[o<<1].mx,t[o<<1|1].mx);
t[o].h=max(t[o<<1].h,t[o<<1|1].h);
}
void build(int o,int l,int r) {
t[o].mx=t[o].h=-inf;
if(l==r) {
t[o].mx=t[o].h=read(9);
return;
}
int mid=l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushUp(o);
}
void pushDown(int o) {
t[o<<1].Change(t[o].add,t[o].hadd);
t[o<<1|1].Change(t[o].add,t[o].hadd);
t[o].add=t[o].hadd=0;
if(t[o].tag) {
t[o<<1].Cover(t[o].cov,t[o].hcov);
t[o<<1|1].Cover(t[o].cov,t[o].hcov);
t[o].tag=t[o].cov=t[o].hcov=0;
}
}
void modify(int o,int l,int r,int L,int R,int k) {
if(l>R or r<L) return;
if(l>=L and r<=R) {
t[o].Cover(k,k);
return;
}
int mid=l+r>>1;
pushDown(o);
modify(o<<1,l,mid,L,R,k);
modify(o<<1|1,mid+1,r,L,R,k);
pushUp(o);
}
void add(int o,int l,int r,int L,int R,int k) {
if(l>R or r<L) return;
if(l>=L and r<=R) {
t[o].Change(k,k);
return;
}
int mid=l+r>>1;
pushDown(o);
add(o<<1,l,mid,L,R,k);
add(o<<1|1,mid+1,r,L,R,k);
pushUp(o);
}
int query(int o,int l,int r,int L,int R) {
if(l>=L and r<=R) return t[o].mx;
int mid=l+r>>1;
pushDown(o);
int ret=-inf;
if(L<=mid)
ret=query(o<<1,l,mid,L,R);
if(R>mid)
ret=max(ret,query(o<<1|1,mid+1,r,L,R));
return ret;
}
int h_query(int o,int l,int r,int L,int R) {
if(l>=L and r<=R) return t[o].h;
int mid=l+r>>1;
pushDown(o);
int ret=-inf;
if(L<=mid)
ret=h_query(o<<1,l,mid,L,R);
if(R>mid)
ret=max(ret,h_query(o<<1|1,mid+1,r,L,R));
return ret;
}
int main() {
n=read(9);
build(1,1,n);
int x,y;
for(int q=read(9);q;--q) {
scanf("%s %d %d",op,&x,&y);
if(op[0]=='Q') {
print(query(1,1,n,x,y),'
');
}
else if(op[0]=='A') {
print(h_query(1,1,n,x,y),'
');
}
else if(op[0]=='P') {
add(1,1,n,x,y,read(9));
}
else {
modify(1,1,n,x,y,read(9));
}
}
return 0;
}