P6792 [SNOI2020] 区间和

solutions

维护一个长为 $n$ 的序列 $a$，支持区间取 $\max$，查询区间最大子段和。

$1 \le n \le 10^5,1 \le q \le 2 \times 10^5,0 \le |a_i|,|x| \le 10^9$。

需要掌握 吉司机线段树 和 KTT。

单点修改维护最大子段和是简单的，线段树维护 $lm,rm,mx,sum$ 分别表示最大前缀和，最大后缀和，最大子段和，区间和。合并就是分讨一下。

区间取 $\max$，还维护一些复杂信息，考虑吉司机线段树，那么只需要考虑区间区间最小值整体加 $x$ 后信息的维护。

参考 区间加区间最大子段和，用一次函数表示 $lm,rm,mx,sum$，其中斜率为对应范围内最小值的个数。KTT 即可。

时间复杂度大概是 $O(n\log^3n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pli pair<LINE,int>
#define MP make_pair
#define fir first
#define sec second
const int N=1e5+10,INF=1e18;
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,a[N];

struct LINE{ int k,b; void add(int v){ b+=k*v; } };
inline LINE operator+(LINE x,LINE y){ return (LINE){x.k+y.k,x.b+y.b}; }
pli mer(LINE x,LINE y){
	if(x.k<y.k||(x.k==y.k&&x.b<y.b)) swap(x,y);
	return x.b>=y.b?MP(x,INF):MP(y,(y.b-x.b)/(x.k-y.k));
}
struct ADJ{
	LINE lm,rm,mx,sum; int mn,se,tim;
	void add(int v){ lm.add(v),rm.add(v),mx.add(v),sum.add(v),mn+=v,tim-=v; }
};
ADJ operator+(ADJ x,ADJ y){
	ADJ res; pli tmp;
	if(x.mn<y.mn) res.mn=x.mn,res.se=min(x.se,y.mn),res.tim=x.tim,y.lm.k=y.rm.k=y.mx.k=y.sum.k=0;
	else if(y.mn<x.mn) res.mn=y.mn,res.se=min(y.se,x.mn),res.tim=y.tim,x.lm.k=x.rm.k=x.mx.k=x.sum.k=0;
	else res.mn=x.mn,res.se=min(y.se,x.se),res.tim=min(x.tim,y.tim);
	res.sum=x.sum+y.sum;
	tmp=mer(x.lm,x.sum+y.lm),res.lm=tmp.fir,chkmin(res.tim,tmp.sec);
	tmp=mer(y.rm,y.sum+x.rm),res.rm=tmp.fir,chkmin(res.tim,tmp.sec);
	tmp=mer(x.mx,y.mx),chkmin(res.tim,tmp.sec);
	tmp=mer(tmp.fir,x.rm+y.lm),res.mx=tmp.fir,chkmin(res.tim,tmp.sec);
	return res;
};

struct SMT{
	#define lc (id<<1)
	#define rc (id<<1|1)
	#define mid (l+r>>1)
	ADJ t[N<<2];
	void psu(int id){ t[id]=t[lc]+t[rc]; }
	void add(int id,int v){ t[id].add(v); }
	void spd(int id){
		if(t[id].mn>t[lc].mn) add(lc,t[id].mn-t[lc].mn);
		if(t[id].mn>t[rc].mn) add(rc,t[id].mn-t[rc].mn);
	}
	void rbui(int id){ if(t[id].tim<0) spd(id),rbui(lc),rbui(rc),psu(id); }
	void bui(int id,int l,int r){
		if(l==r) return t[id]={{1,a[l]},{1,a[l]},{1,a[l]},{1,a[l]},a[l],INF,INF},void();
		bui(lc,l,mid),bui(rc,mid+1,r),psu(id);
	}
	void add(int id,int l,int r,int ql,int qr,int v){
		if(v<=t[id].mn) return; if(ql<=l&&r<=qr&&t[id].mn<v&&v<t[id].se) return add(id,v-t[id].mn),rbui(id); spd(id);
		if(ql<=mid) add(lc,l,mid,ql,qr,v);
		if(qr>mid) add(rc,mid+1,r,ql,qr,v);
		psu(id);
	}
	ADJ ask(int id,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return t[id]; spd(id);
		if(qr<=mid) return ask(lc,l,mid,ql,qr);
		if(ql>mid) return ask(rc,mid+1,r,ql,qr);
		return ask(lc,l,mid,ql,qr)+ask(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}S;

signed main(){

	n=rd,m=rd;
	for(int i=1;i<=n;++i) a[i]=rd;
	
	S.bui(1,1,n);
	for(int i=1,op,l,r,x;i<=m;++i){
		op=rd,l=rd,r=rd; if(op==0) x=rd;
		if(op==0) S.add(1,1,n,l,r,x);
		else printf("%lld\n", max(0ll,S.ask(1,1,n,l,r).mx.b));
	}

	cerr<<clock()<<"ms\n";

	return 0;
}