吉司机线段树学习笔记
给出一个长度为n的数列A同时定义一个辅助数组 B，B开始与 A完全相同。接下来进行了m次操作，构造一个数据结构维护以下五类操作：
-
对于所有i\(\in\)[l,r],将\(A_i\)加上k
-
对于所有i\(\in\)[l,r],将\(A_i\)min(\(A_i\),v)
-
求\(\sum\limits_{i=l}^rA_i\)
-
对于所有i\(\in\)[l,r],求\(A_i\)的最大值
-
对于所有i\(\in\)[l,r],求\(B_i\)的最大值
其中，在每一次操作后，我们都进行一次更新，让\(B_i\leftarrow\max(m,n)\)
对于操作3,4我们非常熟悉，只需要在线段树中维护sum和max即可。
对于操作1同样的，只需要用懒标记tag1标记即可
对于操作5需要维护历史最大值，所以在线段树中我们加上一个变量叫做lszd即一段区间内的历史最大值，然后用懒标记tag2记录修改中最大的修改值即可(eg:在1~5中依次增加2 -5 3，则tag2会记录为2，下传也会下传2)
最难的是操作2,因为线段树是没有取最小值的操作。那么我们可以用一种非常牛逼的操作：就是将线段树维护的max改成fi和se,维护的是一段区间内的第一大的数和第二大的数(为什么要这么做待会再说).那么对于一段要修改的数：我们就可以分类讨论了：
1. 当v>=fi时,直接return.
2. 当se<v<fi时，我们直接让第一大的数加上(v-fi),然后打上懒标记(怎么打待会再说).
3. 当v<=se时,我们继续往下递归,之后再pushup,更新该区间内的sum,fi,se等.
那么应该解决一些问题：
第一个：怎么打懒标记？
解答：既然我们在操作二时已经将一个数分成第一大和其他的数，那么我们的懒标记也要区别对待，对待第一大的其他的数。回想一下，我们要维护两个值：修改的值和修改中的最大的修改值，区别对待后：(第1个)最大值需要修改值,(第2个)最大值修改中的最大的修改值,(第3个)其他的值需要修改值,(第4个)其他的值修改中的最大的修改值
第二个：操作2的时间复杂度？
解答：提供一种(m+n) log n 的做法，看似只要v够小,就会一直执行上面的第三种情况,时间就会退化成n log n,但第三种情况执行完后,fi和se必然会合并,下一次就不会再这样，而修改m次,每一次最多使log n个数改变，故时间复杂度为(m+n) log n的时间复杂度.
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+50,INF=1e15;
ll n,m,a[N];
struct jgt
{
ll sum,fi,se,lszd,cnt;
ll tag1,tag2,tag3,tag4;
}tr[N*8];
void pushup(ll wz)
{
tr[wz].sum=tr[wz*2].sum+tr[wz*2+1].sum;
tr[wz].fi=max(tr[wz*2].fi,tr[wz*2+1].fi);
tr[wz].lszd=max(tr[wz*2].lszd,tr[wz*2+1].lszd);
if(tr[wz*2].fi==tr[wz*2+1].fi)
{
tr[wz].se=max(tr[wz*2].se,tr[wz*2+1].se);
tr[wz].cnt=tr[wz*2].cnt+tr[wz*2+1].cnt;
}
else if(tr[wz*2].fi>tr[wz*2+1].fi)
{
tr[wz].se=max(tr[wz*2].se,tr[wz*2+1].fi);
tr[wz].cnt=tr[wz*2].cnt;
}
else
{
tr[wz].se=max(tr[wz*2].fi,tr[wz*2+1].se);
tr[wz].cnt=tr[wz*2+1].cnt;
}
return ;
}
void pushdown(ll wz,ll l,ll r)
{
ll maxn=max(tr[wz*2].fi,tr[wz*2+1].fi);
ll mid=(l+r)/2;
if(tr[wz*2].fi==maxn)
{
tr[wz*2].sum=tr[wz*2].sum+tr[wz].tag1*tr[wz*2].cnt+(mid-l+1-tr[wz*2].cnt)*tr[wz].tag3;
tr[wz*2].lszd=max(tr[wz*2].lszd,tr[wz*2].fi+tr[wz].tag2);
tr[wz*2].fi+=tr[wz].tag1;
if(tr[wz*2].se!=-INF) tr[wz*2].se+=tr[wz].tag3;
tr[wz*2].tag2=max(tr[wz*2].tag2,tr[wz].tag2+tr[wz*2].tag1);
tr[wz*2].tag4=max(tr[wz*2].tag4,tr[wz].tag4+tr[wz*2].tag3);
tr[wz*2].tag1+=tr[wz].tag1;
tr[wz*2].tag3+=tr[wz].tag3;
}
else
{
tr[wz*2].sum=tr[wz*2].sum+(mid-l+1)*tr[wz].tag3;
tr[wz*2].lszd=max(tr[wz*2].lszd,tr[wz*2].fi+tr[wz].tag4);
tr[wz*2].fi+=tr[wz].tag3;
if(tr[wz*2].se!=-INF) tr[wz*2].se+=tr[wz].tag3;
tr[wz*2].tag2=max(tr[wz*2].tag2,tr[wz].tag4+tr[wz*2].tag1);
tr[wz*2].tag4=max(tr[wz*2].tag4,tr[wz].tag4+tr[wz*2].tag3);
tr[wz*2].tag1+=tr[wz].tag3;
tr[wz*2].tag3+=tr[wz].tag3;
}
if(tr[wz*2+1].fi==maxn)
{
tr[wz*2+1].sum=tr[wz*2+1].sum+tr[wz].tag1*tr[wz*2+1].cnt+(r-mid-tr[wz*2+1].cnt)*tr[wz].tag3;
tr[wz*2+1].lszd=max(tr[wz*2+1].lszd,tr[wz*2+1].fi+tr[wz].tag2);
tr[wz*2+1].fi+=tr[wz].tag1;
if(tr[wz*2+1].se!=-INF) tr[wz*2+1].se+=tr[wz].tag3;
tr[wz*2+1].tag2=max(tr[wz*2+1].tag2,tr[wz].tag2+tr[wz*2+1].tag1);
tr[wz*2+1].tag4=max(tr[wz*2+1].tag4,tr[wz].tag4+tr[wz*2+1].tag3);
tr[wz*2+1].tag1+=tr[wz].tag1;
tr[wz*2+1].tag3+=tr[wz].tag3;
}
else
{
tr[wz*2+1].sum=tr[wz*2+1].sum+(r-mid)*tr[wz].tag3;
tr[wz*2+1].lszd=max(tr[wz*2+1].lszd,tr[wz*2+1].fi+tr[wz].tag4);
tr[wz*2+1].fi+=tr[wz].tag3;
if(tr[wz*2+1].se!=-INF) tr[wz*2+1].se+=tr[wz].tag3;
tr[wz*2+1].tag2=max(tr[wz*2+1].tag2,tr[wz].tag4+tr[wz*2+1].tag1);
tr[wz*2+1].tag4=max(tr[wz*2+1].tag4,tr[wz].tag4+tr[wz*2+1].tag3);
tr[wz*2+1].tag1+=tr[wz].tag3;
tr[wz*2+1].tag3+=tr[wz].tag3;
}
tr[wz].tag1=0;
tr[wz].tag2=0;
tr[wz].tag3=0;
tr[wz].tag4=0;
return ;
}
void BT(ll wz,ll l,ll r)
{
if(l==r)
{
tr[wz].sum=a[l];
tr[wz].fi=a[l];
tr[wz].se=-INF;
tr[wz].lszd=a[l];
tr[wz].cnt=1;
return ;
}
ll mid=(l+r)/2;
BT(wz*2,l,mid);
BT(wz*2+1,mid+1,r);
pushup(wz);
return ;
}
void add(ll wz,ll l,ll r,ll le,ll ri,ll k)
{
pushdown(wz,l,r);
if(le<=l&&ri>=r)
{
tr[wz].sum=tr[wz].sum+(r-l+1)*k;
tr[wz].fi+=k;
if(tr[wz].se!=-INF) tr[wz].se+=k;
tr[wz].lszd=max(tr[wz].lszd,tr[wz].fi);
tr[wz].tag1+=k;
tr[wz].tag2=max(tr[wz].tag2,tr[wz].tag1);
tr[wz].tag3+=k;
tr[wz].tag4=max(tr[wz].tag4,tr[wz].tag3);
return ;
}
ll mid=(l+r)/2;
if(le<=mid) add(wz*2,l,mid,le,ri,k);
if(ri>mid) add(wz*2+1,mid+1,r,le,ri,k);
pushup(wz);
return ;
}
void gai(ll wz,ll l,ll r,ll le,ll ri,ll v)
{
if(le<=l&&ri>=r)
{
if(v>=tr[wz].fi) return ;
if(v>tr[wz].se)
{
tr[wz].sum=tr[wz].sum+tr[wz].cnt*(v-tr[wz].fi);
tr[wz].tag1=tr[wz].tag1+v-tr[wz].fi;
tr[wz].fi=v;
tr[wz].tag2=max(tr[wz].tag2,tr[wz].tag1);
return ;
}
}
pushdown(wz,l,r);
ll mid=(l+r)/2;
if(le<=mid) gai(wz*2,l,mid,le,ri,v);
if(ri>mid) gai(wz*2+1,mid+1,r,le,ri,v);
pushup(wz);
return ;
}
ll querysum(ll wz,ll l,ll r,ll le,ll ri)
{
if(le<=l&&ri>=r) return tr[wz].sum;
pushdown(wz,l,r);
ll mid=(l+r)/2,zh=0;
if(le<=mid) zh+=querysum(wz*2,l,mid,le,ri);
if(ri>mid) zh+=querysum(wz*2+1,mid+1,r,le,ri);
return zh;
}
ll queryfi(ll wz,ll l,ll r,ll le,ll ri)
{
if(le<=l&&ri>=r) return tr[wz].fi;
pushdown(wz,l,r);
ll mid=(l+r)/2,zd=-INF;
if(le<=mid) zd=max(zd,queryfi(wz*2,l,mid,le,ri));
if(ri>mid) zd=max(zd,queryfi(wz*2+1,mid+1,r,le,ri));
return zd;
}
ll querylszd(ll wz,ll l,ll r,ll le,ll ri)
{
if(le<=l&&ri>=r) return tr[wz].lszd;
pushdown(wz,l,r);
ll mid=(l+r)/2,zd=-INF;
if(le<=mid) zd=max(zd,querylszd(wz*2,l,mid,le,ri));
if(ri>mid) zd=max(zd,querylszd(wz*2+1,mid+1,r,le,ri));
return zd;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
BT(1,1,n);
ll op,l,r,k,v;
for(ll i=1;i<=m;i++)
{
scanf("%lld",&op);
if(op==1)
{
scanf("%lld %lld %lld",&l,&r,&k);
add(1,1,n,l,r,k);
}
else if(op==2)
{
scanf("%lld %lld %lld",&l,&r,&v);
gai(1,1,n,l,r,v);
}
else if(op==3)
{
scanf("%lld %lld",&l,&r);
printf("%lld\n",querysum(1,1,n,l,r));
}
else if(op==4)
{
scanf("%lld %lld",&l,&r);
printf("%lld\n",queryfi(1,1,n,l,r));
}
else if(op==5)
{
scanf("%lld %lld",&l,&r);
printf("%lld\n",querylszd(1,1,n,l,r));
}
}
return 0;
}