狗家VO

tamaimasenako

本帖最后由 tamaimasenako 于 2021-4-10 13:27 编辑

bigboss789 发表于 2021-4-10 10:50
请问大佬RMQ是什么？

倍增法的一种应用。
大意是对每个点，预处理它右侧长度为2^k的区间。比如这个数列
3,2,4,3,8,4,5
对第一个元素，我们可以预处理出f[0][0] = 3, f[0][1] = 3, f[0][2] = 4, f[0][3] = 8
f[i][k] = max(f[i][k-1], f[i + (1 << k-1)][k-1])
根据这个式子从后往前dp，总共预处理时间是O(nlogn)。
最后query的时候，比如query(int l, int r); //[l, r]
我们只需输出 max(f[l][k], f[r + 1 - (1<<k)][k])就行，其中k使得2^k刚好>=[l,r]的一半
比如对[1, 7]，我们输出 max(f[1][2], f[4][2]), 其中f[1][2]覆盖了1, 2, 3, 4, f[4][2]覆盖了4, 5, 6, 7，刚好覆盖了这个区间。
这样的话，query的回答是O(1)

复制代码

[/i][/i]

bigboss789

第二轮的followup， what if the events arrive in arbitrary order? 大家有什么想法？

lazkey

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

shuofeng11

楼主能否大致讲一下第二题followup思路? “what if there are spikes? what if the events arrive in arbitrary order?” 谢谢

zanbin2046

第一题deque O(n) 的算法。

xiana406

第一题的题目简单但是可以的做法各式各样，真的考察人的水平。哭了。

jeeerice

菜鸡表示第一题只能浅显的想到brute force。。。难过的要哭了...

yyyyyz

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yezhengli_mr9

tamaimasenako 发表于 2021-4-9 04:39
我的想法是
query 一次：直接暴搜
query 数次，不支持修改：RMQ

后两种都能现场写？厉害