题目 题解
Solution
对于任意区间右端点
i
i
i，其左端点取值在
l
l
l,
r
r
r之间，若左端点为
m
m
m，则
v
v
v为
m
a
x
(
s
u
m
[
i
]
−
s
u
m
[
m
−
1
]
)
max(sum[i]-sum[m-1])
max(sum[i]−sum[m−1])，显然这里
i
i
i是不变的，所以可以用
s
t
st
st表查询
m
m
m的位置，然后计算v。 现将所有右端点扫一遍，然后扔到堆里面，堆中节点记录的是决策，即右端点
i
i
i，左端点区间，优先级由
v
v
v决定 然后取出堆顶，
v
v
v加到
a
n
s
ans
ans里去，分裂
[
l
,
r
]
[l,r]
[l,r]为
[
l
,
m
−
1
]
[l,m-1]
[l,m−1]和
[
m
+
1
,
r
]
[m+1,r]
[m+1,r]，
R
M
Q
RMQ
RMQ出新的
v
v
v，再将分裂后的区间加到堆里 重复
k
k
k次
Code
#include<bits/stdc++.h>
using namespace std
;
const int N
=500002;
struct node
{
int i
,l
,m
,r
,v
;
friend bool operator <(node a
,node b
){return a
.v
<b
.v
;}
}t
;
priority_queue
<node
>q
;
int lg
[N
],L
,R
,i
,j
,n
,k
,a
[N
],tmp
,st
[N
][20],l
,r
,m
;
long long ans
;
inline char gc(){
static char buf
[100000],*p1
=buf
,*p2
=buf
;
return p1
==p2
&&(p2
=(p1
=buf
)+fread(buf
,1,100000,stdin),p1
==p2
)?EOF:*p1
++;
}
inline int rd(){
int x
=0,fl
=1;char ch
=gc();
for (;ch
<48||ch
>57;ch
=gc())if(ch
=='-')fl
=-1;
for (;48<=ch
&&ch
<=57;ch
=gc())x
=(x
<<3)+(x
<<1)+(ch
^48);
return x
*fl
;
}
int get(int x
,int y
){
x
--;y
--;
int l
=lg
[y
-x
+1];
if (a
[st
[x
][l
]]<a
[st
[y
-(1<<l
)+1][l
]]) return st
[x
][l
]+1;
return st
[y
-(1<<l
)+1][l
]+1;
}
int main(){
n
=rd();k
=rd();L
=rd();R
=rd();
lg
[0]=-1;
for (i
=1;i
<=n
;i
++) a
[i
]=rd()+a
[i
-1],lg
[i
]=lg
[i
>>1]+1,st
[i
][0]=i
;
for (j
=1;j
<=lg
[n
];j
++)
for (i
=0;i
+(1<<j
)-1<=n
;i
++)
if (a
[st
[i
][j
-1]]<a
[st
[i
+(1<<j
-1)][j
-1]]) st
[i
][j
]=st
[i
][j
-1];
else st
[i
][j
]=st
[i
+(1<<j
-1)][j
-1];
for (i
=1;i
<=n
;i
++){
l
=max(i
-R
+1,1);r
=max(i
-L
+1,1);
if (i
-l
+1<L
) continue;
m
=get(l
,r
);
q
.push((node
){i
,l
,m
,r
,a
[i
]-a
[m
-1]});
}
while (k
--){
t
=q
.top();q
.pop();
ans
+=t
.v
;
l
=t
.l
;r
=t
.r
;m
=t
.m
;
if (l
<m
){
tmp
=get(l
,m
-1);
q
.push((node
){t
.i
,l
,tmp
,m
-1,a
[t
.i
]-a
[tmp
-1]});
}
if (m
<r
){
tmp
=get(m
+1,r
);
q
.push((node
){t
.i
,m
+1,tmp
,r
,a
[t
.i
]-a
[tmp
-1]});
}
}
printf("%lld",ans
);
}
