抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

CF280D k-Maximum Subsequence Sum 线段树

发布于：2019年7月13日

传送门

题面大意：

长度为nn的数列，支持两种操作：
1.1.修改某个位置的值
2.2.询问区间[l,r][l,r]里选出至多kk个不相交的子段和的最大值。 一共有mm个操作

解法：

暴力

dpdp+滚动数组（在本地卡进2s2s）
模拟赛的时候有人用这个方法AA了
dp[i][j][p]dp[i][j][p]表示进行到a[i]a[i]，用了jj个区间，a[i]a[i]选不选
大力转移即可

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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
namespace bf{
	int dp[2][25][2];
	inline int query(int l,int r,int k){
		memset(dp,0,sizeof(dp));
		for (register int i=l;i<=r;++i){
			for (register int j=1;j<=k;++j){
				dp[i&1][j][0]=max(dp[!(i&1)][j][1],dp[!(i&1)][j][0]);
				dp[i&1][j][1]=max(dp[!(i&1)][j-1][0],dp[!(i&1)][j][1])+a[i];
				dp[i&1][j][1]=max(dp[i&1][j][1],dp[!(i&1)][j-1][0]+a[i]);
			}
		}
		int ans=-0x7fffffff;
		for (register int i=0;i<=k;++i){
			ans=max(ans,max(dp[r&1][i][1],dp[r&1][i][0]));
		}
		return ans;
	}
}
using namespace bf;
int main(){
	int n=read();
	for (register int i=1;i<=n;++i){
		a[i]=read();
	}
	int q=read();
	while (q--){
		int opr=read();
		if (opr==0){
			int i=read(),val=read();
			a[i]=val;
		}
		else {
			int l=read(),r=read(),k=read();
			printf("%d\n",query(l,r,k));
		}
	}
}

正解

毒瘤线段树，维护1818个值：
sumsum 区间和
l,rl,r 区间左右边界
maxsmaxs 最大子段和
minsmins 最小子段和
maxslmaxsl 最大子段和左边界
maxsrmaxsr最大子段和右边界
minslminsl最小子段和左边界
minsrminsr最小子段和右边界
maxl,minlmaxl,minl最大，最小前缀和
maxlp,minlpmaxlp,minlp最大，最小前缀和右端点（显然左端点确定）
maxr,minrmaxr,minr最大，最小后缀和
maxrp,minrpmaxrp,minrp最大，最小后缀和左端点
flagflag翻转标记

每次取最大子段和，ans+=ans+=最大子段和，
然后把最大子段和的区间每个数∗−1*-1，如果最大子段和<=0<=0或者操作次数>k>k退出

你肯定会有疑问：这样怎么保证取出来不超过kk段？

设原数列最大子段和为∑p=ijap\sum_{p=i}^{j} a_p：
a1a2a3...aiai+1ai+2...aj−1aj....ana_1 a_2 a_3 ... a_i a_{i+1} a_{i+2} ... a_{j-1} a_{j} .... a{n}
取出最大子段和，区间∗−1*-1
a1a2a3...−ai−ai+1−ai+2...−aj−1−aj....ana_1 a_2 a_3 ... -a_i -a_{i+1} -a_{i+2} ... -a_{j-1} -a_{j} .... a{n}
假设操作一次后最大子段和变为∑p=i′j′ap\sum_{p=i'}^{j'} a_p，其中i′<ji'<j且j<j′j<j'
a1a2a3...ai′ai′+1ai′+2...aj′−1aj′....ana_1 a_2 a_3 ... a_{i'} a_{i'+1} a_{i'+2} ... a_{j'-1} a_{j'} .... a{n}
两次结果相加，中间部分抵消：
ai+ai+1+ai+2...+aj−1+aj+ai′+ai′+1+ai′+2+...aj′−1+aj′a_i + a_{i+1} + a_{i+2} ... + a_{j-1} + a_{j} +a_{i'} + a_{i'+1} + a_{i'+2} +... a_{j'-1} + a_{j'}
=ai+...+ai′−1+aj+1+...+aj′=a_i+...+a_{i'-1}+a_{j+1}+...+a_{j'}
结果变为两段，即k=2k=2
其他情况自己脑补一下，就会发现其实每次操作后段数最多+1+1

贪心的正确性可以用费用流证明，这里贴一篇博客

p.s.不要忘记恢复修改过的线段树

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
bool DBG=true;
namespace SegmentTree{
	struct node{
		int sum;//区间和
		int l,r;//区间左右边界
		int maxs;//最大子段和
        int mins;//最小子段和
		int maxsl;//最大子段和左边界
        int maxsr;//最大子段和右边界
		int minsl;//最小子段和左边界
        int minsr;//最小子段和右边界
		int maxl,minl;//最大，最小前缀和
		int maxlp,minlp;//最大，最小前缀和右端点（显然左端点确定） 
		int maxr,minr;//最大，最小后缀和
		int maxrp,minrp;//最大，最小后缀和左端点
		bool flag;//翻转标记
	}tree[MAXN<<2];
	inline void sw(int &a,int &b){int temp=a;a=b;b=temp;}
    inline void re(int &a){a=-a;}
	inline void Rev(int i){//翻转tree[i]
        re(tree[i].sum);
		sw(tree[i].maxs,tree[i].mins);
        re(tree[i].maxs),re(tree[i].mins);
		sw(tree[i].maxsl,tree[i].minsl);
		sw(tree[i].maxsr,tree[i].minsr);
		sw(tree[i].maxl,tree[i].minl);
        re(tree[i].maxl),re(tree[i].minl);
		sw(tree[i].maxlp,tree[i].minlp);
		sw(tree[i].maxr,tree[i].minr);
        re(tree[i].maxr),re(tree[i].minr);
		sw(tree[i].maxrp,tree[i].minrp);
		tree[i].flag^=1;
	}
	#define lc i<<1
	#define rc i<<1|1
    #define nd tree[i]
	inline void pushdown(int i){
		if (tree[i].flag) Rev(lc),Rev(rc),tree[i].flag=0;
	}
	node operator + (const node &A,const node &B){
        //这里不能写错，要不然调一年
        node C;
        C.l=A.l,C.r=B.r;
        C.sum=A.sum+B.sum;
        C.flag=false;
        //维护maxs,mins,maxsl,minsl
        if (max(A.maxs,B.maxs)>A.maxr+B.maxl){
            if (A.maxs>B.maxs){
                C.maxs=A.maxs;
                C.maxsl=A.maxsl;
                C.maxsr=A.maxsr;
            }
            else {
                C.maxs=B.maxs;
                C.maxsl=B.maxsl;
                C.maxsr=B.maxsr;
            }
        }
        else {
            C.maxs=A.maxr+B.maxl;
            C.maxsl=A.maxrp;
            C.maxsr=B.maxlp;
        }
        if (min(A.mins,B.mins)<A.minr+B.minl){
            if (A.mins<B.mins){
                C.mins=A.mins;
                C.minsl=A.minsl;
                C.minsr=A.minsr;
            }
            else {
                C.mins=B.mins;
                C.minsl=B.minsl;
                C.minsr=B.minsr;
            }
        }
        else {
            C.mins=A.minr+B.minl;
            C.minsl=A.minrp;
            C.minsr=B.minlp;
        }
        //维护maxl,minl,维护其端点
        if (A.sum+B.maxl>A.maxl){
            C.maxl=A.sum+B.maxl;
            C.maxlp=B.maxlp;
        }
        else {
            C.maxl=A.maxl;
            C.maxlp=A.maxlp;
        }
        if (A.sum+B.minl<A.minl){
            C.minl=A.sum+B.minl;
            C.minlp=B.minlp;
        }
        else {
            C.minl=A.minl;
            C.minlp=A.minlp;
        }
        //维护maxr,minr,维护其端点
        if (A.maxr+B.sum>B.maxr){
            C.maxr=A.maxr+B.sum;
            C.maxrp=A.maxrp;
        }
        else {
            C.maxr=B.maxr;
            C.maxrp=B.maxrp;
        }
        if (A.minr+B.sum<B.minr){
            C.minr=A.minr+B.sum;
            C.minrp=A.minrp;
        }
        else {
            C.minr=B.minr;
            C.minrp=B.minrp;
        }
        return C;//快乐地return 
	}
    inline void pushup(int i){
        bool temp=tree[i].flag;
        tree[i]=tree[lc]+tree[rc];
        tree[i].flag=temp;
    }
    inline void Set(int i,int val){
        nd.sum=nd.maxs=nd.mins=nd.maxl=nd.minl=nd.maxr=nd.minr=val;
    }
    void Build(int l,int r,int i){
        tree[i].flag=0;
        if (l==r){
            tree[i].l=l,tree[i].r=l;
            Set(i,a[l]);
            nd.maxsl=nd.maxsr=nd.minsl=nd.minsr=nd.maxlp=nd.minlp=nd.maxrp=nd.minrp=l;
            return ;
        }
        int mid=(l+r)>>1;
        Build(l,mid,lc);
        Build(mid+1,r,rc);
        pushup(i);
    }
    node Query(int L,int R,int i){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i];
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (mid>=R) return Query(L,R,lc);
        else if (mid<L) return Query(L,R,rc);
        else return Query(L,R,lc)+Query(L,R,rc);
    }
    void Update(int L,int R,int i){//区间*-1
        if (L<=tree[i].l&&tree[i].r<=R){
            Rev(i);
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (mid>=R) Update(L,R,lc);
        else if (mid<L) Update(L,R,rc);
        else Update(L,R,lc),Update(L,R,rc);
        pushup(i);
    }
    void Update_pos(int index,int i,int val){//单点修改
        if (tree[i].l==tree[i].r){
            Set(i,tree[i].flag?-val:val);
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (index<=mid) Update_pos(index,lc,val);
        else Update_pos(index,rc,val);
        pushup(i);
    }
}
using namespace SegmentTree;
int L[MAXN],R[MAXN];
int main(){
    int n=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,n,1);
    int q=read();
    while (q--){
        int opr=read();
        if (opr==1){
            int l=read(),r=read(),k=read();
            int tot=0,ans=0;
            for (register int i=1;i<=k;++i){//贪心
                node Q=Query(l,r,1);
                if (Q.maxs<=0) break;
                ans+=Q.maxs;
                L[++tot]=Q.maxsl,R[tot]=Q.maxsr;
                Update(L[tot],R[tot],1);
            }
            for (register int i=1;i<=tot;++i){//恢复线段树
                Update(L[i],R[i],1);
            }
            printf("%d\n",ans);
        }
        else {
            int i=read(),val=read();
            Update_pos(i,1,val);
        }
    }
}
相关文章
P3380 【模板】二逼平衡树（树套树）BZOJ 4025 二分图CF145E Lucky Queries 线段树CF316 E3. Summer Homework基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/6ce8a7e1.html

更新于：2022年6月14日

题解

贪心

线段树

暴力

毒瘤

费用流

评论