原题地址

题目描述

给定一列多米诺骨牌的高度和底端横坐标,求若要让推动第x块至少使第y块倒下,需要加长区间内的多米诺骨牌的总长度。

样例

输入

输出

样例解释

(样例的第四个询问)

思路

倍增。

维护一块骨牌右边最近的碰不到的骨牌编号和距离。

询问直接log累加就行了。。。

代码