暑期集训提高篇与

RMQ与LCA05数学试点班刁瑞什么是RMQRMQ=RangeMinimalQuery也即对一个区间的最小值询问，也可以是最大值例如：数列3，5，2，9，1，4，6询问：[2,4]的最大值？……9询问：[6,7]的最小值？……4在线与离线在线算法：用比较长的时间作预处理，但是等信息充足以后每次回答询问只需要用比较少的时间离线算法：把所有的询问读入，然后一起把所有的询问回答完成例如：Fibonacci的在线算法复杂度为O(n+q)，离线算法复杂度为O(nlogq)RMQ的在线算法动态规划？dp[i][j]表示[i,j]区间内的最小值，则dp[i][i]=a[i]dp[i][j+1]=min{dp[i][j],a[j+1]}效率？O(n^2)预处理，O(1)回答问题能不能更高效呢？RMQ的算法改进考虑最小值具有如下特点：[2,6]的最小值和[3,9]的最小值中的最小者等于[2,9]的最小值。最小值可以合并！如果我们预处理得到了[a,b]的最小值，[c,d]的最小值且c<=b，则[a,d]的最小值可以在O(1)时间内算出。这说明DP的时候我们不必计算出所有的dp[i][j]也可以。SparseTable算法简称：ST算法dp[i][j]表示区间[i,i+2^j-1]的最小值，则dp[i][0]=a[0]dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]}这样可以得到所有的dp[i][j]SparseTable算法如果询问区间为[s,t]，则只需要取k=(int)log2(t-s+1)RMQ[s,t]=min{dp[s][k],dp[t-2^k+1][k]}这时候预处理的算法复杂度仅为O(nlogn)而回答问题仍然是O(1)的复杂度实际操作的时候，我们不一定用log来计算k，也可以通过二分查找，因为它不见得比log慢其他算法RMQ问题也可以使用“线段树”解决下次提高篇讲座将会介绍NKOJ1752Frequentvalues给定一个递增数列，要求找到询问区间上的出现次数最多的数出现了几次-1-11111310101023？1110？4510？3NKOJ1752Frequentvalues由于给定的数列是有序的，可以先转化为另一种存储方式，使得新数列中的每个数是原数列中的元素重复次数，例如-1-111113101010转化为：2413辅助sum数组用来二分查找：26710对于输入的区间，利用二分查找找到它在新数列中对应的区间，除了边界要特殊处理以外，余下的部分就是RMQ了POJ2823SlidingWindowdp[i][j]占用内存太大，需要使用“滚动数组”考虑询问的区间长度均相等，求RMQ[s,t]=min{dp[s][k],dp[t-2^k+1][k]}

k=(int)log2(t-s+1)，所需要的k是定值，因此递推求dp[i][j]的时候，只需要保留一个dp[i][k]即可，递推的时候可以随时将已求出的dp[i][j]覆盖掉RMQ习题POJ3264BalancedLineup（比较简单）NKOJ1752Frequentvalues（转化）POJ2823SlidingWindow（滚动数组）NKOJ：POJ：LCALCA=LeastCommonAncestors最近公共祖先问题它是针对一棵树的问题，与RMQ有联系ABCDEFGHIJKLME和G的LCA为AL和J的LCA为DK和F的LCA为BTarjan离线算法并查集father[u]表示u点的父亲通过father[father[father[…..u…..]]]可以求得u的某一层父亲节点可以看出LCA(u,v)总是会等于u的某一层父亲函数findfather(v)找到v点当前的最终父亲复杂度O(n+q)Tarjan离线算法VoidLCA(u){

father[u]=u;

对于u的每个儿子v{

LCA(v);

father[v]=u;

}

color[u]=1;

对于Q(u)中所有的v

如果color[v]==1

u和v的LCA=findfather(v);

}LCA转化为RMQ深度优先遍历树，每经过一个点，就记录下这个点的深度和标号如此得到两个数组：深度数组和标号数组，元素均为2*n-1个对于标号数组中的任何两个点，他们的下标在深度数组中对应一个区间，这个区间的最小值就对应着两个点的LCAABCDEFGHIJKLM深度数列={0，1，2，3，2，1，2，1，0，1，0，1，2，1，2，3，2，3，2，1，2，1，2，1，0}

标号数列={A，B，E，K，E，B，F，B，A，C，A，D，G，D，H，L，H，M，H，D，I，D，J，D，A}±1RMQ注意到深度数列有一个特点，每两个相邻元素的差均为±1，我们称这样的RMQ问题为±1RMQ±1RMQ有O(n)预处理，O(1)的算法，但