单调栈求第一个小于某个数的位置。
思路
这道题目需要求的是 a[l] % a[l + 1]… % a[r], 我们需要知道的是每次取模,如果a < b,那么取模没用,如果a > b,那么取模减小的数字至少是a的一半(我不知道啊。。。),那么这样的话,每次询问,最多取模的次数是Log(n), 问题就是我们需要预处理出小于当前数字的第一个数字的位置。这就用到了单调栈了。
1 |
|
云腾致雨,露结为霜
单调栈求第一个小于某个数的位置。
这道题目需要求的是 a[l] % a[l + 1]… % a[r], 我们需要知道的是每次取模,如果a < b,那么取模没用,如果a > b,那么取模减小的数字至少是a的一半(我不知道啊。。。),那么这样的话,每次询问,最多取模的次数是Log(n), 问题就是我们需要预处理出小于当前数字的第一个数字的位置。这就用到了单调栈了。
1 | #include <iostream> |