Phys Ed Online(单调队列/单调栈/rmq/好题)

题目 题意：给定一个体育馆，每天有不同的票价 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