OI - k-Maximum Subsequence Sum(Codeforces)


开始一轮数据结构线段树复习……

题目链接:Codeforces 280D


Part1. 题意

给出一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$;有 $m$ 次操作,操作包括下面两种:

  1. 0 x y 将 $a_x$ 的值改为 $y$;
  2. 1 l r k 在区间 $[l,r]$ 里选择至多 $k$ 个不相交的区间,使得这些区间中的所有数之和最大,求这个最大值(也可以什么区间都不选,答案就是 0)。

数据规模:
$1\le n,m\le10^5$,$-500\le a_i\le500$;
对于操作 1 :$1\le x\le n$,$-500\le y\le500$;
对于操作 2 :$1\le l\le r\le n$,$1\le k\le20$;


Part2. 解析

Part2/1. 最大子段和

先考虑如果不存在修改(操作1),只有一次询问:在 $[l,r]$ 中选择至多 $k$ 个区间。

如果 $k=1$,就是一个非常经典的“最大子段和

Hint. 最大子段和
给定原数列,求一个子区间,使得其中的数之和最大。

可以用线段树维护 ①区间最大子段和 mx[l,r]、②从区间的最左端开始的最大子段和 mxL[l,r]、③从区间的最右端开始的最大子段和 mxR[l,r]、④区间和 sum[l,r]

1
2
3
4
5
6
7
8
9
10
11
//计算 [l,r] 的最大子段和
mx[l,r] = max{ mx[l,m]/*全在左边*/ , mx[m+1,r]/*全在右边*/ , mxR[l,m]+mxL[m+1,r]/*左右区间拼接*/ }

//计算 [l,r] 靠左的最大子段和
mxL[l,r] = max{ mxL[l,m]/*全在左边*/ , sum[l,m]+mxL[m+1,r]/*左右拼接*/ }

//计算 [l,r] 靠右的最大子段和,同上
mxR[l,r] = max{ mxR[m+1,r] , mxR[l,m]+sum[m+1,r] }

//计算区间和
sum[l,r] = sum[l,m]+sum[m+1,r]

这样就可以维护了 ~

Part2/2. 带区间反转的最大子段和

先不要管为什么需要这个操作

考虑操作:将指定区间 $[l,r]$ 内的每个数乘上 $-1$;要求动态维护最大子段和

仍然考虑线段树,首先线段树里就需要反转的懒标记 lzy[l,r] 了。

然后看看当一个区间 $[l,r]$ 反转了,它的 mx[l,r], mxL[l,r], mxR[l,r], sum[l,r] 会怎么变 ——

  • 最简单的就是 sum[l,r] ,直接乘上 $-1$ 就可以了。
  • mx[l,r], mxL[l,r], mxR[l,r] 的值都会乘上 $-1$;它们原来是最大值,那么乘上 $-1$ 后就变成了对应的最小值……原来的最小值乘上 $-1$ 也就变成了对应的最大值。

突然发现还要维护 ①区间最小子段和 mn[l,r]、②从区间最左端开始的最小子段和 mnL[l,r]、③从区间最右端开始的最小子段和 mnR[l,r];维护方法一样。

然后反转的操作就是:

1
2
3
4
5
swap( mn[l,r] , mx[l,r] )
swap( mnL[l,r] , mxL[l,r] )
swap( mnR[l,r] , mxR[l,r] )

mn[l,r] mx[l,r] mnL[l,r] mxL[l,r] mnR[l,r] mxR[l,r] sum[l,r] *= -1

Part2/3. k次最大子段和

下面这种情况,我们已经求出了一个最大子段和,想要根据这个情况推出选两个区间时的最大子段和:

png1

上图的蓝色块是第一次选择的区间,“第二次选择”有三种方案:

  1. 不包括蓝色块的区间:png2
  2. 从蓝色块中选出一段区间断开:png3
  3. 选一段区间与蓝色块相交(不包含),删去中间部分:png4

这样我们就可以得到两个区间(而且包含了所有情况),发现这两个区间的数之和 为“前后两次选取区间的数之和 - 重叠部分的数之和”。

于是就得到一种方案:选取第一个区间后,将该区间反转,再选第二个区间,所以一直做最大子段和就可以了。

然后发现……我们不仅要求出最大子段和是多少,还要求出最大子段和到底是哪一段……所以

Part2/4. 结构体优化

定义一个“区间”结构体

1
2
3
4
struct NODE{
int val,Vl,Vr;
NODE(int _val=0,int _Vl=0,int _Vr=0):val(_val),Vl(_Vl),Vr(_Vr){}
};

val 表示该区间的数之和,Vl,Vr 分别表示区间的左右端点。然后就可以重载运算符了:

1
2
3
4
5
6
7
8
//比较两个区间大小,其实就是比较两个区间的元素之和的大小(这样就可以用 max,min 了)
bool operator <(const NODE Pa,const NODE Pb){return Pa.val<Pb.val;}
bool operator >(const NODE Pa,const NODE Pb){return Pa.val>Pb.val;}
//两个相邻区间相连接,注意连接顺序:把Pa和Pb接起来
NODE operator +(const NODE Pa,const NODE Pb){return NODE(Pa.val+Pb.val,Pa.Vl,Pb.Vr);}
//区间整体乘上一个数字 Pb
NODE operator *(const NODE Pa,const int Pb){return NODE(Pa.val*Pb,Pa.Vl,Pa.Vr);}
NODE operator *=(NODE &Pa,const int Pb){Pa.val*=Pb;return Pa;}

我觉得这样打包过后可以简化代码……


Part3. 源代码

【代码有点长……点击展开/折叠代码
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
/*Lucky_Glass*/
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5;

int n,m;
int Ia[N+3];

struct NODE{
int val,Vl,Vr;
NODE(int _val=0,int _Vl=0,int _Vr=0):val(_val),Vl(_Vl),Vr(_Vr){}
};
bool operator <(const NODE Pa,const NODE Pb){return Pa.val<Pb.val;}
bool operator >(const NODE Pa,const NODE Pb){return Pa.val>Pb.val;}
NODE operator +(const NODE Pa,const NODE Pb){return NODE(Pa.val+Pb.val,Pa.Vl,Pb.Vr);}
NODE operator *(const NODE Pa,const int Pb){return NODE(Pa.val*Pb,Pa.Vl,Pa.Vr);}
NODE operator *=(NODE &Pa,const int Pb){Pa.val*=Pb;return Pa;}
struct RESULT{
NODE mid,lef,rig,sum;
RESULT(NODE _m,NODE _l,NODE _r,NODE _s):mid(_m),lef(_l),rig(_r),sum(_s){}
};
struct SEGTREE{
NODE Emx[N*4],EmxL[N*4],EmxR[N*4],Emn[N*4],EmnL[N*4],EmnR[N*4],Esum[N*4];
bool Zrev[N*4];
void GetRev(int u){
swap(Emx[u],Emn[u]);swap(EmxL[u],EmnL[u]);swap(EmxR[u],EmnR[u]);
Emx[u]*=-1;Emn[u]*=-1;EmxL[u]*=-1;EmnL[u]*=-1;EmxR[u]*=-1;EmnR[u]*=-1;
Esum[u]*=-1;
}
void PushUp(int u){
Emx[u]=max(max(Emx[u<<1],Emx[u<<1|1]),EmxR[u<<1]+EmxL[u<<1|1]);
Emn[u]=min(min(Emn[u<<1],Emn[u<<1|1]),EmnR[u<<1]+EmnL[u<<1|1]);
EmxL[u]=max(EmxL[u<<1],Esum[u<<1]+EmxL[u<<1|1]);
EmnL[u]=min(EmnL[u<<1],Esum[u<<1]+EmnL[u<<1|1]);
EmxR[u]=max(EmxR[u<<1|1],EmxR[u<<1]+Esum[u<<1|1]);
EmnR[u]=min(EmnR[u<<1|1],EmnR[u<<1]+Esum[u<<1|1]);
Esum[u]=Esum[u<<1]+Esum[u<<1|1];
}
void PushDown(int u,int Vl,int Vr){
if(Vl<Vr && Zrev[u]){
GetRev(u<<1);Zrev[u<<1]=!Zrev[u<<1];
GetRev(u<<1|1);Zrev[u<<1|1]=!Zrev[u<<1|1];
}
Zrev[u]=false;
}
void Build(int u,int Vl,int Vr){
if(Vl==Vr){
Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Ia[Vl],Vl,Vl);
return;
}
int Vm=(Vl+Vr)>>1;
Build(u<<1,Vl,Vm);Build(u<<1|1,Vm+1,Vr);
PushUp(u);
}
void Modify(int u,int Vl,int Vr,int Upos,int Uval){
if(Vr<Upos || Upos<Vl) return;
if(Vl==Vr){
Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Uval,Upos,Upos);
return;
}
PushDown(u,Vl,Vr);
int Vm=(Vl+Vr)>>1;
Modify(u<<1,Vl,Vm,Upos,Uval);Modify(u<<1|1,Vm+1,Vr,Upos,Uval);
PushUp(u);
}
void Reverse(int u,int Vl,int Vr,int Ul,int Ur){
if(Vr<Ul || Ur<Vl) return;
if(Ul<=Vl && Vr<=Ur){
Zrev[u]=!Zrev[u];
GetRev(u);
return;
}
PushDown(u,Vl,Vr);
int Vm=(Vl+Vr)>>1;
Reverse(u<<1,Vl,Vm,Ul,Ur);
Reverse(u<<1|1,Vm+1,Vr,Ul,Ur);
PushUp(u);
}
RESULT Query(int u,int Vl,int Vr,int Ul,int Ur){
if(Ul<=Vl && Vr<=Ur) return RESULT(Emx[u],EmxL[u],EmxR[u],Esum[u]);
PushDown(u,Vl,Vr);
int Vm=(Vl+Vr)>>1;
if(Ur<Vm+1) return Query(u<<1,Vl,Vm,Ul,Ur);
if(Vm<Ul) return Query(u<<1|1,Vm+1,Vr,Ul,Ur);
RESULT Rl=Query(u<<1,Vl,Vm,Ul,Ur),Rr=Query(u<<1|1,Vm+1,Vr,Ul,Ur);
return RESULT(max(max(Rl.mid,Rr.mid),Rl.rig+Rr.lef),max(Rl.lef,Rl.sum+Rr.lef),max(Rr.rig,Rl.rig+Rr.sum),Rl.sum+Rr.sum);
}
}seg;

stack< pair<int,int> > Sclr;
int main(){
// freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&Ia[i]);
scanf("%d",&m);
seg.Build(1,1,n);
while(m--){
int Iopt;scanf("%d",&Iopt);
if(Iopt){
int Il,Ir,Ik,Vans=0;scanf("%d%d%d",&Il,&Ir,&Ik);
while(Ik--){
RESULT Rr=seg.Query(1,1,n,Il,Ir);
NODE fRr=max(Rr.mid,max(Rr.lef,Rr.rig));
if(fRr.val<0) break;
Sclr.push(make_pair(fRr.Vl,fRr.Vr));
Vans+=fRr.val;
seg.Reverse(1,1,n,fRr.Vl,fRr.Vr);
}
printf("%d\n",Vans);
while(!Sclr.empty()){
seg.Reverse(1,1,n,Sclr.top().first,Sclr.top().second);
Sclr.pop();
}
}
else{
int Ipos,Ival;scanf("%d%d",&Ipos,&Ival);
seg.Modify(1,1,n,Ipos,Ival);
}
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!

0%