题目
题意：给定一个体育馆，每天有不同的票价
a
i
a_i
ai。有多次查询（原题是说不同的学生，一个意思），每次查询连续从
[
l
,
r
]
[l,r]
[l,r]去体育馆的最小花费。
- 一张票从它使用第一次开始，连续的k天都有效。即第i天使用，到i+k-1天都有效。
- 之前买的票（还未使用的情况），可以留到后边再使用。
- 对于第i天去体育馆，如果手头有之前已经开启使用的、还未过期的票，则无需开销；否则，需要启用新的票，如果手头没有票，则需要购买当天的、至少一张票。
官方题解
思路：第一天肯定需要买票。接下来的k-1天都不需要花费票钱，到了第
l
+
k
l+k
l+k天，则需要花费一张票，为使开销最小，取
m
i
n
(
a
l
,
a
l
+
1
,
.
.
.
,
a
l
+
k
)
min(a_l,a_{l+1},...,a_{l+k})
min(al,al+1,...,al+k)；到了第
l
+
2
∗
k
l+2*k
l+2∗k天，则取
m
i
n
(
a
l
,
.
.
.
,
a
l
+
2
∗
k
)
min(a_l,...,a_{l+2*k})
min(al,...,al+2∗k)。
定义
b
i
=
m
i
n
[
a
i
−
k
,
a
i
]
b_i=min[a_{i-k},a_i]
bi=min[ai−k,ai]
因此，连续去
[
l
,
r
]
[l,r]
[l,r]的体育馆的最小开销为
a
n
s
=
a
l
+
b
l
+
k
+
m
i
n
(
b
l
+
k
,
b
l
+
2
∗
k
)
+
.
.
.
+
m
i
n
(
b
l
+
k
,
b
l
+
2
∗
k
,
.
.
.
,
b
l
+
t
k
)
,
l
+
t
k
<
=
r
<
l
+
(
t
+
1
)
∗
k
ans=a_l+b_{l+k}+min(b_{l+k},b_{l+2*k})+...+min(b_{l+k},b_{l+2*k},...,b_{l+tk}),l+tk
