RMQ和人民权的故事(Range Minimum Query)

说国王带领士兵出征打仗,回来队伍排成一排,国王说,想看看士兵们谁用掉的弹药最多,即剩下的弹药最少,就说明谁打仗最勇猛。虽然弹药和勇猛并不成正比,就像猫捉耗子,花纹和捕鼠能力并无关系,可国王偏是要这么认为我也没办法。国王这不是没事找事吗?

于是国王命令士兵们站成一排,国王又闲得慌了,他不从第一个开始检查起,偏偏是脑袋一发热,得了,从您检查起吧,还美其名曰人民群众的眼睛雪亮,能发现一直呆工事里的逃兵,还起了个找抽的名字“人民权(Reng Ming Quan,简称RMQ)”。你说这士兵们能不郁闷吗,好好的驾驶坦克飞机,没用上步枪手枪,怎么又成逃兵了?孟姜女哭长城,我们哭坦克飞机。

国王拉来军师,军师又拿个小本本来记录。他说,大体上上,第一步,首先,在一切开始之前,准备工作是,好吧军事也忘了。军事回去翻了一天书,知道了,第一大步就是比较相邻两个人,你知道,站在一起的基本是伙伴,万一串通反叛国王怎么办?第一个和第二个比较,第二个和第三个比较,一路下来,到倒数第二个比下来,淘汰一半。

接下来,比较距离两个的。也就是第一个和第三个,第二个和第四个,一直下去。原因是三人串通也危险,保不齐发展出来个三角恋什么的。奥不对,哪有这东西,军师是说搞不好发展出金三角银三角的危险地带可就麻烦了。

国王等不及了,说这得等啥时候去啊?军师只好加快速度。原来不是有个科学家说,生产资料增长是线性,人口是平方增长么?那么我也来个人口平方普查好了。任命一个平方队长,听着好像异次元高科技的概念,但其实是个吃空饷的闲职,只在统计国王看不顺眼的逃兵上有点用。原来分别检查2的0次方,2的1次方,现在该一次性增加2的2次方,也就是第1个和5个,第2个和第6个,一个一个来,不让任何一个逃走,就这样,下一大步再统计2的3次方,就这样。士兵武器普查完了。

现在到国王来检查了,这可简单了,原来按平方普查的数,所以国王只要找个在他查找人数内的最大平方数,把这个数供起来,祭献几个战俘也是可以的。国王找到那个幸运的被他抽中的家伙,然后按编号再找下一个家伙,由于他们都是平方队长,所以国王把他们一比就行了。

于是我们的军师又连升三级,以及一批玩忽职守的逃兵被处决,尽管百姓还是吃不饱穿不暖,但我们的王国又繁荣了一点。

Leave a Reply