Lvat_s Blog

最近集训出了很多SGTB(SeGmentTree Beats!)的题目,所以被迫来学习这个冬令营上的黑科技。。

这题照着其他人写的程序理解了几个小时，然后自己写了一发居然是最快的。。。

记录一下自己对于这题的理解吧

输入的操作分别对应:

1.区间加

2.区间max(0,v)

3.区间赋值

4.询问单点值

5.询问单点历史最值

然后我一开始试图维护十来个标记然后暴力搞。。然后就不会了

然后膜了一下其他人的程序和lzz的冬令营课件，总算有了一点理解了

这题关键在于单点询问，所以我们仅仅把区间当成一整个标记，每次下传后就清零

然后问题在于两个操作：询问历史最值和区间max

我们先不管询问历史最值

其实我们进行一番转化后可以发现,其实123操作都可以对应到一个(x,y)（加上x对y取max）上（这是对于一个区间的标记）

1:区间加v -> (v,INF)

2:区间max(0,v) -> (v,0)

3.区间赋值为v -> (-INF,v);

这很显然吧。。

然后我们考虑两个标记的合并，这里我还是想了一下的

设旧标记为A,新标记为B

那么我们进行合并就变成了(A.x+B.x,max(A.y+B.x,B.y))

为什么是这样呢？

首先我们考虑如果A.x+B.x,那么就直接相当于普通线段树的Add操作，明显可行

而max(A.y+B.x,B.y)则表示如果旧标记产生的最大值为A.y,那么我们最终要取的值要么就是旧标记的A.y加上新标记要加上的值(因为旧标记可能取A.y)，要么就是新标记要取的B.y（感觉我这句话比较意识流啊），当然是在这两个数里面选一个最大值了

于是我们就处理完了没有历史最值询问的操作

但是这题是有历史最值询问的。。好坑啊

那么我们考虑再加上两个标记mx,addmx表示当前区间的历史最值和要加上去的值的历史最值

那么我们继续考虑合并标记

同样，我们设(X,Y)表示mx和addmx两个值（偷懒），那么我们继续设以前的旧标记为A，用来更新旧标记的新标记为B

那么历史最值可以怎么构成？可以由旧标记的历史最值、新标记的历史最值，或者是旧标记的当前值加上新标记的的历史最大加值。

前两个很好理解，但是最后一个是什么意思呢？

首先，新标记的历史最大加值可以用这样一段话来叙述：“这一段区间曾经加过这么大的值”

那么我们每次拿旧标记当前的值加上新标记的历史最大加值，就意味着这个合并后的标记曾经在某个时刻达到了这个可能的最大值

因为每次更新标记时都是自顶向下，那么没有被更新的旧标记的值一定是当前值，如果被更改了那么之前一定在这里下传过标记，所以这样是对的

而我们再考虑addmx可以怎么构成

显然这个值可能的取值为：旧标记的addmx,新标记的addmx加上旧标记的add

为什么又是这么取值呢？

第一种情况显然。第二种情况因为新标记的历史最大加值此时没有经过任何更新，也就是和旧标记一点关联也没有

而因为add的定义和题目的描述(就是上面的小写标记)，add标记一定不会小于0

那么我们当然需要加上这个add值（新标记此前不可能加过add标记），这样能让解更优

那么你可能会问:为什么不能让旧标记的历史最值加上新标记的add呢？

因为新标记是用来更新旧标记的，所以这样可能重复的加所以不行

这仅仅是个人的理解，我觉得真是漏洞百出，具体的证明lzz冬令营课件里面有，反正我没有看太懂。。。

我真是太弱了

这真是一篇意识流的题解

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m;
long long a[500005];
const long long INF=1000000000000000ll;

template<typename T>void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct SegTree{
int l,r;
long long v,mx,add,addmx;
SegTree(){}
SegTree(long long V,long long MX,long long ADD,long long ADDMX){v=V;mx=MX;add=ADD;addmx=ADDMX;}
SegTree(int L,int R,long long V,long long MX,long long ADD,long long ADDMX){l=L;r=R;v=V;mx=MX;add=ADD;addmx=ADDMX;}
}tree[2000005],tmp;

SegTree Update(SegTree A,SegTree B){
return SegTree(A.l,A.r,max(A.v+B.add,B.v),max(max(A.mx,B.mx),A.v+B.addmx),max(A.add+B.add,-INF),max(A.addmx,A.add+B.addmx));
}

void Pushdown(int rt){
tree[rt*2]=Update(tree[rt*2],tree[rt]);
tree[rt*2+1]=Update(tree[rt*2+1],tree[rt]);
tree[rt]=SegTree(tree[rt].l,tree[rt].r,0,0,0,0);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
	tree[rt].addmx=tree[rt].add=tree[rt].v=tree[rt].mx=a[l];
	return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
}

void Change(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt]=Update(tree[rt],tmp);return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt*2,l,r);
if(r>mid)Change(rt*2+1,l,r);
}

long long Query(int rt,int pos,int id){
if(tree[rt].l==tree[rt].r){return id?tree[rt].mx:tree[rt].v;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(rt*2,pos,id);
if(pos>mid)return Query(rt*2+1,pos,id);
}

int main(){
freopen("164.in","r",stdin);
freopen("164.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++)Read(a[i]);
Build(1,1,n);
for(int i=1;i<=m;i++){
    int opt,l,r,v;
    Read(opt);
    if(opt==1){Read(l);Read(r);Read(v);tmp=SegTree(0,0,v,v);Change(1,l,r);}
    if(opt==2){Read(l);Read(r);Read(v);tmp=SegTree(0,0,-v,-v);Change(1,l,r);}
    if(opt==3){Read(l);Read(r);Read(v);tmp=SegTree(v,v,-INF,-INF);Change(1,l,r);}
    if(opt==4){Read(v);printf("%lld\n",Query(1,v,0));}
    if(opt==5){Read(v);printf("%lld\n",Query(1,v,1));}
}
return 0;
}