Monsters And Spells(dp/rmq)

题目 题意：有n只怪兽，每只怪兽在 k i k_i ki​时间点会出现，且生命值为 h i h_i hi​。现在我们需要消灭这 n n n只怪兽。由于我们每次打气功，都需要从1开始累计，比如上一秒是打的气功是x，那么这一秒可以打x+1，或者选择重新开始，气功为1。如果上一秒没有打气功，则这一秒只能打1。要消灭这 n n n只小怪兽，我们总共需要消耗的最小气功是多少。

思路： 先根据每只小怪兽的生命值，计算消灭这只小怪兽，需要从哪里开始打气功 p o s i pos_i posi​，比如 k i = 6 , h i = 3 k_i=6,h_i=3 ki​=6,hi​=3，说明我们需要在时间点6-3+1=4的位置开始打气功。如果要批量处理连续区间内的小怪兽，我们需要计算区间 [ l , r ] [l,r] [l,r]的最小打气功的开始位置 p p p，然后计算从 p p p到 k r k_r kr​的气功总和即可。

由于本题的n比较小，可以支持 n 2 n^2 n2的复杂度。我们可以用dp。令 d p i dp_i dpi​表示从i位置结束需要的最小气功。那么 d p i = d p j − 1 + d e a l ( j , i ) , ( 0 < j < = i ) dp_i = dp_{j-1} + deal(j,i),(0