Znzryb's Blog
0%

 P4513 【小白逛公园】（维护最大子串和）

Posted on Edited on

思路讲解

参考题解

https://www.luogu.com.cn/article/1o6edp6y

zkw线段树写法

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
// 参考了（抄了）beta99999 的提交  https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
// AC https://www.luogu.com.cn/record/230419677 最大子段和
template <typename T,typename value_type> struct base_segtree{
    int n,sz;
    vector<value_type> tr;
    static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
    // zkw线段树开两倍大小，identity为默认值
    base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}    
    T *derived() { return static_cast<T*>(this); }
    void pushup(int o){
        tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
    }

    // zkw选配  
    int dis(int o){return __lg(sz)-__lg(o);}    // 倒数第几层？有倒数第0层
    int len(int o){return 1<<dis(o);}   // （直接调用就可以，就是左闭右开区间长度）
    int le(int o){return (o<<dis(o))-sz; }  // 左闭
    int rr(int o){return (o+1<<dis(o))-sz;} // 右开
    void build(){
        for(int o=sz-1;o>=1;--o){
            derived()->pushup(o);
        }
    }
    template<typename D> 
    void update(int l,D x){
        tr[l+sz]=x;
        int o=l+sz;
        for(int i=1;i<=__lg(o);++i){
            derived()->pushup(o>>i);
        }
    }
    value_type query(int l, int r){
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) resl=T::op(resl,tr[l++]);
            if(r&1) resr=T::op(tr[--r],resr);
        }
        return T::op(resl,resr);
    }
    void assign(int i,value_type a){
        tr[i+sz]=a;
    }
};
struct State{
    ll pre,suf,mx,sum;
    // State(ll pre,ll suf,ll mx,ll sum):pre(pre),suf(suf),mx(mx),sum(sum) {}
};
struct segtree:base_segtree<segtree, State>{
    static constexpr State identity={-INF,-INF,-INF,0};
    static State op(const State &a,const State &b){
        return {
		        // 这个是在重新计算 A 和 B 合并以后的区间的最大前缀和。
            max(b.pre+a.sum,a.pre),
            // 这个是在重新计算 A 和 B 合并以后的区间的最大后缀和。
            max(b.suf,b.sum+a.suf),
            // 这个是在计算 A 和 B 合并以后区间的最大子段和。
            max({a.mx,b.mx,a.suf+b.pre}),
            // 这个就比较简单，这个其实就是在计算区间的和，A 和 B 合并以后的区间的和。
            a.sum+b.sum
        };
    }
    segtree(ll n):base_segtree<segtree, State>(n){}
};
constexpr State segtree::identity;

AC代码

AC

https://www.luogu.com.cn/record/199579498

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e5)+10,MIN=-1e17+9,que=MAXN-10;
ll N,M;
// P4513 小白逛公园
// https://www.luogu.com.cn/problem/P4513
struct Tree {
	int l=0,r=0;
	ll maxLeft,maxRight,sum,ans;
}tr[MAXN*4];
// 区间合并代码
inline void merge(int k) {
	int lson = k*2,rson=k*2+1;
	tr[k].sum=tr[lson].sum+tr[rson].sum;
	//                                    一定包含左端点且相连
	tr[k].maxLeft=max(tr[lson].maxLeft,tr[lson].sum+tr[rson].maxLeft);
	//                                     一定包含右端点且相连
	tr[k].maxRight=max(tr[rson].maxRight,tr[lson].maxRight+tr[rson].sum);
	//                                         相连且为最优
	tr[k].ans=max({tr[lson].ans,tr[rson].ans,tr[lson].maxRight+tr[rson].maxLeft});
}
inline Tree mergeTr(Tree lt,Tree rt) {
	Tree res;
	res.sum=lt.sum+rt.sum;
	//                                    一定包含左端点且相连
	res.maxLeft=max(lt.maxLeft,lt.sum+rt.maxLeft);
	//                                     一定包含右端点且相连
	res.maxRight=max(rt.maxRight,lt.maxRight+rt.sum);
	//                                         相连且为最优
	res.ans=max({lt.ans,rt.ans,lt.maxRight+rt.maxLeft});
	return res;
}
void buildTree(int x,int l,int r) {
	if(l==r) {
		tr[x].l=tr[x].r=l;
		tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=MIN;
		return;
	}
	tr[x].l=l,tr[x].r=r;
	tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=MIN;
	int mid=l+r>>1;
	buildTree(x*2,l,mid);
	buildTree(x*2+1,mid+1,r);
}
//           树上位置，位置，  分数
void change(int x,int pos,ll sc) {
	if(tr[x].l==pos && tr[x].r==pos) {
		tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=sc;
		return;
	}
	int mid=tr[x].l+tr[x].r>>1;
	// 在右子树
	if(pos>mid) change(x*2+1,pos,sc);
	else change(x*2,pos,sc);// 在左子树
	merge(x);
}
Tree query(int x,int l,int r) {
	if(l<=tr[x].l && tr[x].r<=r) {
		return tr[x];
	}
	int mid=tr[x].l+tr[x].r>>1;

	if(l>mid) {
		// 区间全部在右树
		return query(x*2+1,l,r);
	}else{
		// 区间全部在左树
		if(r<=mid) {
			return query(x*2,l,r);
		}else {
			Tree ltree,rtree;
			ltree=query(x*2,l,r);
			rtree=query(x*2+1,l,r);
			return mergeTr(ltree,rtree);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	buildTree(1,1,N);
	for(int i=1;i<=N;++i) {
		ll a;
		cin>>a;
		change(1,i,a);	// 懒得建树
	}
	for(int i=1;i<=M;++i) {
		ll op;
		cin>>op;
		if(op==1) {
			ll a,b;
			cin>>a>>b;
			if(a>b) swap(a,b);
			cout<<query(1,a,b).ans<<'\n';
		}else {
			int pos;ll s;
			cin>>pos>>s;
			change(1,pos,s);
		}
	}
	return 0;
}
/*
AC https://www.luogu.com.cn/record/199579498
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3

*/

心路历程（WA，TLE，MLE……）