Rmq

题目链接 题意： # 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。

题目链接 题意： # 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。

题目链接 题意：定义一个函数F．． For exampe: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12)

hdu 4123 题目链接 题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是:添加虚点！

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

hdu 3530题目链接 题意：给出n个数，m,k，问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A.

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。

hdu2142题目链接 题意：有n个订单和可以在m小时内制作月饼 接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼 接下来一行t,s表示制作的月饼可以保质t天，每保质一天需要花费s的价值 接下来m行表示从第0小时开始在该时间制作月饼的花费的价值 求完成所有订单消耗的最小价值

poj 3368 题目链接 题意：给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle…

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。

hdu2888题目链接 题意：问某个矩阵内的最大值，并且问最大值是否是在四个角中出现。 思路：二维rmq.需要注意数组稍微开大1就会MLE,因为是四维数组，一维大一点，整个就会大很多==。

1636: [Usaco2007 Jan]Balanced Lineup # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss]