栗子栗子

小trick之最值式拆分转化为RMQ

最值式拆分转化为RMQ

RMQ

RMQ,即Range Minimum(Maximum) Query,区间最值查询(区间和也放入其中好了23333)

使用但不包括于区间的最值,求和等可统计信息的查询。可以支持插入删除修改操作

常见的RMQ解决方案有

ST(查询最值,不支持修改),树状数组(查询和,前缀最值,支持修改),线段树(查询和,最值,支持修改)

这三种方法在此不作详述

Trick级应用(代码暂欠)

有的时候很多看似不好下手的问题均可以转化为区间最值问题,下面举栗

FJNUOJ新生赛某题(好像该OJ挂了,说一下大致题意)

给定一个数列,最多有十万个数,要求找到$i\neq j$,使得$a_i+a_j+|i-j|$最大

思路:

显然暴力枚举$i$和$j$会超时

我们不妨假设$i \lt j$,将原式子拆分,变成$(a_i-i)+(a_j+j)$

那么我们只需要枚举$j$,找到在这之前的$a_i-i$的最大值即可,复杂度$O(n)$

51nod 1593

大致题意是一个环,环上有n个数$hi$,两个数之间有权值$dist{i,i+1}$

每次给出一段不能走的区间,这样剩下一条链,要求在链上找到两点$x,y$,使得$2(h_x+hy)+dist{x,y}$最大

思路:

跟上一题一样,依然将要求的式子拆分

考虑到环的问题,将原环拆分成链并拓展,然后计$di=dist{1,i}$

这样我们只需找到$x,y$使得$(2h_y+d_y)+(2h_x-d_x)$最大

然后维护区间最值,细节处理即可

总结

题目中往往需要我们求出牵涉到若干个下标的最值,这个时候暴力枚举往往会超时

而拆分不失为一种解决该问题的好手段

通过合理地加强条件,以及若干项的添加,划分,合并,转化为若干个组合式的最值之和

然后分别针对这些组合式进行RMQ操作即可