[DS记录]P6792 [SNOI2020] 区间和
command_block
2021-07-18 23:15:26
**题意** ： 维护一个长为 $n$ 的序列 $A$ (可能有负数) ，支持下列操作 ：
- 给出 $l,r,x$ ，将 $k\in [l,r]$ 的 $a_k\leftarrow \max(a_k,x)$
- 求区间 $[l,r]$ 的最大子段和。
$n\leq 10^5,m\leq 2\times 10^5$ ，时限$\texttt{3s}$。
------------
> 感谢 @Fuyuki 的指导。
根据区间取 $\max$ 区间求和的经典 $\text{Seg-Beats}$ ，考虑维护最小值。
记 区间和、区间最小值、区间最小值个数 为 $s,x,c$。
记 最大前缀、最大后缀、最大子段和 为 $ls,rs,ms$。
一并维护 $ls,rs,ms$ 中含有的最小值个数，记为 $lc,rc,mc$ 。在仅修改最小值时就能快速计算影响。
但是，即使仅修改了最小值，上述三者的最优方案也有可能发生变化。
我们为 最大前缀、最大后缀 记一个“最小击破时间”，即最小值增大到多少才能使得某个方案变化。记为 $t$。（注意到 $ms$ 的方案变化一定是因为 $ls$ 或 $rs$ 的方案变化，无需考虑其击破时间）
在合并节点 $l,r$ 时 ：
$u.t\leftarrow l.t,r.t$ 。
- 若 $u.ls=l.s+r.ls$ ，则随着最小值的增大， $l.s+r.ls$ 一定比 $l.ls$ 大，无贡献。
- 若 $u.ls=l.ls$ ，则 $l.s+r.ls$ 击破 $l.ls$ 所需增量为 $\Big\lceil\dfrac{l.ls-l.s-r.ls}{l.c+r.lc-l.lc}\Big\rceil$
$u.rs$ 的贡献也是类似的，不再赘述。
这样，我们就容易判断修改是否会影响 $ls,rs,ms$ 的方案，并适时暴力递归。
分析复杂度。
由于我们只会增大权值， $ls,rs$ 的长度只会单调增加，于是只会发生 $O(n\log n)$ 次“击破”事件。
对于每次“击破”事件，需要来到对应节点，这花费 $O(\log n)$ 的递归复杂度。
总复杂度为 $O(n\log^2n+m\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 200500
using namespace std;
const int INF=1000000010;
struct Node{
int x,c,tg,lc,rc,mc,t;ll s,ls,rs,ms;
// t 也考虑了区间次小值
inline void Init(int a){
s=x=a;c=1;
if (a<=0)ls=rs=ms=lc=rc=mc=t=0;
else {ls=rs=ms=a;lc=rc=mc=1;t=INF;}
}
inline void ladd(int tg2){
tg=tg2;swap(x,tg2);tg2=x-tg2;
s+=1ll*tg2*c;ls+=1ll*tg2*lc;
rs+=1ll*tg2*rc;ms+=1ll*tg2*mc;
}
}a[1<<18|500];
inline void up(int u){
int l=u<<1,r=u<<1|1,c1,c2;ll s1,s2;
a[u].s=a[l].s+a[r].s;
a[u].x=min(a[l].x,a[r].x);
bool fl=(a[l].x==a[u].x),fr=(a[r].x==a[u].x);
a[u].c=fl*a[l].c+fr*a[r].c;
a[u].t=min(
min(a[l].t,a[r].t),
min(fl ? a[l].t : a[l].x-1,fr ? a[r].t : a[r].x-1)
);
c1=fl*a[l].lc;c2=fl*a[l].c+fr*a[r].lc;
s1=a[l].ls;s2=a[l].s+a[r].ls;
if (s2>s1){a[u].ls=s2;a[u].lc=c2;}
else {
a[u].ls=s1;a[u].lc=c1;
if (c2>c1)a[u].t=min((ll)a[u].t,a[u].x+(s1-s2)/(c2-c1));
}
c1=fr*a[r].rc;c2=fr*a[r].c+fl*a[l].rc;
s1=a[r].rs;s2=a[r].s+a[l].rs;
if (s2>s1){a[u].rs=s2;a[u].rc=c2;}
else {
a[u].rs=s1;a[u].rc=c1;
if (c2>c1)a[u].t=min((ll)a[u].t,a[u].x+(s1-s2)/(c2-c1));
}
if (a[l].rs+a[r].ls>max(a[l].ms,a[r].ms)){
a[u].ms=a[l].rs+a[r].ls;
a[u].mc=fl*a[l].rc+fr*a[r].lc;
}else if (a[l].ms>a[r].ms)
{a[u].ms=a[l].ms;a[u].mc=fl*a[l].mc;}
else {a[u].ms=a[r].ms;a[u].mc=fr*a[r].mc;}
}
int x[MaxN];
void build(int l,int r,int u)
{
a[u].tg=INF;
if (l==r){a[u].Init(x[l]);return ;}
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
inline void ladd(int u){
if (a[u].tg!=INF){
if (a[u].tg>a[u<<1].x)
a[u<<1].ladd(a[u].tg);
if (a[u].tg>a[u<<1|1].x)
a[u<<1|1].ladd(a[u].tg);
a[u].tg=INF;
}
}
int wfl,wfr,wfc;ll tms,trs;
void chg(int l,int r,int u)
{
if (wfc<=a[u].x)return ;
if (wfl<=l&&r<=wfr&&wfc<=a[u].t)
{a[u].ladd(wfc);return ;}
if (l==r){a[u].Init(wfc);return ;}
int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)chg(l,mid,u<<1);
if (mid<wfr)chg(mid+1,r,u<<1|1);
up(u);
}
void qry(int l,int r,int u)
{
if (wfl<=l&&r<=wfr){
tms=max(max(tms,a[u].ms),trs+a[u].ls);
trs=max(trs+a[u].s,a[u].rs);
return ;
}int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)qry(l,mid,u<<1);
if (mid<wfr)qry(mid+1,r,u<<1|1);
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)scanf("%d",&x[i]);
build(1,n,1);
for (int i=1,op;i<=m;i++){
scanf("%d%d%d",&op,&wfl,&wfr);
if (op==0){scanf("%d",&wfc);chg(1,n,1);}
else {tms=trs=0;qry(1,n,1);printf("%lld\n",tms);}
}return 0;
}
```