这个题有点意思。
注意到这个题目是区间修改单点查询。
如果对序列建线段树的话，意味着不需处理信息的合并，只要把tag处理好就可。
还有一个常用的套路就是扫描线。
讲两种做法。
做法一
我们先往正常的线段树方向想。
首先把操作统一一下，操作2可以看作变成 ，操作3可以看作变成 。于是我们把操作都变成了操作1。
如果我们对每个操作看作一个映射的话，那么它的图象是一段常函数接一段斜率为1的一次函数的形状。（因为有+和取max）。容易知道这样形状的映射是可以复合的，复合后还是这样的形状。于是我们可以考虑维护这样的映射。我们把tag做成这样的函数，处理一下tag的合并（映射的复合），就可以解决单点询问值的操作。（把标记放到底再拿初始值映射一下）
而它还有一个询问单点历史最大值的操作。容易想到我们也可以对最大值维护一个映射。还是要解决合并的问题，两个映射合并时考虑最大值可能在第二个映射之前取到，也可能在第二个映射之后取到。那么就是两个图象取上方的部分，仍是这样的形状，故是可合并的。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e5+50;
const LL inf=1e16;
int n,m,a[N];bool fl[N*4];
int read(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+c-48,c=getchar();
return x;
}
struct Laz{
LL x,y;//对于一个映射记录它顶点（拐角）的坐标
LL calc(LL a)const{return a<=x?y:y+a-x;}
void fix(){if(x<-inf)y+=-inf-x,x=-inf;if(x>inf)x=inf;}
Laz operator +(const Laz &b){//这个是映射的复合
if(y>=b.x)return (Laz){x,b.calc(y)};
else return(Laz){b.x-y+x,b.y};
}
Laz operator *(const Laz &b){//这个是两个映射取上方
Laz c=*this,d=b;
if(c.y<d.y)swap(c,d);
if(d.calc(c.x)<=c.y)return c;
else return (Laz){d.x+c.y-d.y,c.y};
}
}laz[N*4],mx[N*4];
void build(int x,int l,int r){
if(l==r){laz[x]=mx[x]=(Laz){-inf,-inf};fl[x]=1;return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void change(int x,int l,int r,int ql,int qr,Laz d,Laz m){
if(l>=ql&&r<=qr){
if(fl[x])mx[x]=mx[x]*(laz[x]+m),laz[x]=laz[x]+d;
else mx[x]=m,laz[x]=d;
mx[x].fix();laz[x].fix();
fl[x]=1;return;
}
int mid=(l+r)>>1;
if(fl[x]){
change(x<<1,l,mid,1,n,laz[x],mx[x]);
change(x<<1|1,mid+1,r,1,n,laz[x],mx[x]);
fl[x]=0;
}
if(ql<=mid)change(x<<1,l,mid,ql,qr,d,m);
if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,d,m);
}
LL query(int x,int l,int r,int p,int op){
if(l==r)return (op?mx[x]:laz[x]).calc(a[l]);
int mid=(l+r)>>1;
if(fl[x]){
change(x<<1,l,mid,1,n,laz[x],mx[x]);
change(x<<1|1,mid+1,r,1,n,laz[x],mx[x]);
fl[x]=0;
}
if(p<=mid)return query(x<<1,l,mid,p,op);
return query(x<<1|1,mid+1,r,p,op);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
for(int i=1,op,l,r,x;i<=m;i++){
op=read();
if(op<=3)l=read(),r=read();
x=read();
if(op<=3){
Laz d;
if(op==1)d=(Laz){-inf,x-inf};
else if(op==2)d=(Laz){x,0};
else d=(Laz){inf,x};
change(1,1,n,l,r,d,d);
}
else printf("%lld\n",query(1,1,n,x,op-4));
}
return 0;
}
做法二
还是考虑把操作统一一点。三操作可以看作-inf再+x。
我们来考虑单独一个数时这些操作会对它产生什么影响。我们维护一个当前值，顺序扫这些操作，若当前值小于0则把它置成0。等等..这不是在求最大后缀和么？历史最大值就是我们每次都对当前值取个max。这不是在求最大子段和么？
好。我们现在发现只要我们对于一个数有对他影响的完整的操作序列，我们就能通过线段树求一个前缀的最大子段和及最大后缀和来求解。但是我们有多个数啊。。没关系，看到一个操作只对一个区间的数有影响，这让我们想到了扫描线。于是这题就愉快地解决啦！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e5+50;
const long long inf=5.5e14;
int read(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+c-48,c=getchar();
return x;
}
int n,m,T,q,cnt[N];long long ans[N],a[N];
struct node{long long x;int p,id;};
vector<node>v[N],Q[N];
LL fix(LL x){if(x<-inf)return -inf;if(x>inf)return inf;return x;}
struct Mes{
LL sum,ml,mr,mm;
void fix(){sum=::fix(sum);ml=::fix(ml);mr=::fix(mr);mm=::fix(mm);}
Mes operator +(const Mes &b){
Mes z;
z.sum=sum+b.sum;
z.ml=max(ml,sum+b.ml);
z.mr=max(b.mr,mr+b.sum);
z.mm=max(mr+b.ml,max(mm,b.mm));
z.fix();
return z;
}
}t[N*4];
void change(int x,int l,int r,int p,long long d){
if(l==r){
if(d==inf)cnt[l]++;
else if(d==-inf)cnt[l]--;
else a[l]+=d;
if(cnt[l]>0)t[x].sum=inf;
else if(cnt[l]<0)t[x].sum=-inf;
else t[x].sum=a[l];
t[x].ml=t[x].mr=t[x].mm=t[x].sum>0?t[x].sum:0;
return;
}
int mid=(l+r)>>1;
if(p<=mid)change(x<<1,l,mid,p,d);
else change(x<<1|1,mid+1,r,p,d);
t[x]=t[x<<1]+t[x<<1|1];
}
Mes query(int x,int l,int r,int qr){
if(r<=qr)return t[x];
int mid=(l+r)>>1;
if(qr<=mid)return query(x<<1,l,mid,qr);
return query(x<<1,l,mid,qr)+query(x<<1|1,mid+1,r,qr);
}
int main(){
n=read();m=read();T=1;
for(int i=1,x=0,y;i<=n;i++)y=read(),v[i].push_back((node){y-x,1}),x=y;
for(int i=1,op,l,r,x;i<=m;i++){
op=read();
if(op<=3)l=read(),r=read();
x=read();
if(op==3)T++,v[l].push_back((node){-inf,T}),v[r+1].push_back((node){inf,T}),op=1;
if(op==1)T++,v[l].push_back((node){x,T}),v[r+1].push_back((node){-x,T});
else if(op==2)T++,v[l].push_back((node){-x,T}),v[r+1].push_back((node){x,T});
else if(op==4)Q[x].push_back((node){T,0,++q});
else Q[x].push_back((node){T,1,++q});
}
for(int i=1;i<=n;i++){
for(int j=0;j<v[i].size();j++)
change(1,1,T,v[i][j].p,v[i][j].x);
for(int j=0;j<Q[i].size();j++){
Mes x=query(1,1,T,Q[i][j].x);
ans[Q[i][j].id]=Q[i][j].p?x.mm:x.mr;
}
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
值得一提的是这两个做法都有涉及inf。这个可坑了我一把呜呜呜。inf必须设成比涉及到的最大的数还大，在这题是 。如果数据构造让 个inf加起来，就会溢出qwq
所以我们要杜绝这种情况。。详情看两个代码中的fix函数。