题目
分析
考虑一个
m
a
x
x
(
x
,
l
,
r
)
maxx(x,l,r)
maxx(x,l,r)表示以左端点为
x
x
x，右端点在
[
l
∼
r
]
[l\sim r]
[l∼r]的范围内的最大值，那么维护的最大值也就是
s
[
m
x
]
−
s
[
l
−
1
]
s[mx]-s[l-1]
s[mx]−s[l−1]，而只有
m
x
mx
mx是变动的，所以可以用RMQ去求解，把这个三元组扔进一个大根堆里面，跑
k
k
k次，但是处理完一个三元组后需要把它拆成
m
a
x
x
(
x
,
l
,
m
x
−
1
)
maxx(x,l,mx-1)
maxx(x,l,mx−1)和
m
a
x
x
(
x
,
m
x
+
1
,
r
)
maxx(x,mx+1,r)
maxx(x,mx+1,r)，重新扔进大根堆
代码
#include <cstdio>
#include <cctype>
#include <queue>
#define min(a,b) ((a)<(b)?(a):(b))
#define rr register
using namespace std
;
const int N
=500011; long long ans
;
int n
,k
,L
,R
,s
[N
],f
[N
][19],lg
[N
];
struct rec
{
int x
,l
,r
,mx
;
bool operator <(const rec
&t
)const{
return s
[mx
]-s
[x
-1]<s
[t
.mx
]-s
[t
.x
-1];
}
};
priority_queue
<rec
>q
;
inline signed iut(){
rr
int ans
=0,f
=1; rr
char c
=getchar();
while (!isdigit(c
)) f
=(c
=='-')?-f
:f
,c
=getchar();
while (isdigit(c
)) ans
=(ans
<<3)+(ans
<<1)+(c
^48),c
=getchar();
return ans
*f
;
}
inline signed query(int l
,int r
){
rr
int z
=lg
[r
-l
+1],p1
=f
[l
][z
],p2
=f
[r
-(1<<z
)+1][z
];
return s
[p1
]>s
[p2
]?p1
:p2
;
}
signed main(){
n
=iut(); k
=iut(); L
=iut(); R
=iut();
for (rr
int i
=1;i
<=n
;++i
) s
[i
]=s
[i
-1]+iut();
for (rr
int i
=2;i
<=n
;++i
) lg
[i
]=lg
[i
>>1]+1;
for (rr
int i
=1;i
<=n
;++i
) f
[i
][0]=i
;
for (rr
int j
=1;(1<<j
)<=n
;++j
)
for (rr
int i
=1;i
+(1<<j
)-1<=n
;++i
){
rr
int p1
=f
[i
][j
-1],p2
=f
[i
+(1<<(j
-1))][j
-1];
f
[i
][j
]=s
[p1
]>s
[p2
]?p1
:p2
;
}
for (rr
int i
=1;i
+L
-1<=n
;++i
) q
.push((rec
){i
,i
+L
-1,min(i
+R
-1,n
),query(i
+L
-1,min(i
+R
-1,n
))});
while (k
--){
rr rec t
=q
.top(); q
.pop(); ans
+=s
[t
.mx
]-s
[t
.x
-1];
if (t
.l
!=t
.mx
) q
.push((rec
){t
.x
,t
.l
,t
.mx
-1,query(t
.l
,t
.mx
-1)});
if (t
.mx
!=t
.r
) q
.push((rec
){t
.x
,t
.mx
+1,t
.r
,query(t
.mx
+1,t
.r
)});
}
return !printf("%lld",ans
);
}
