RMQ

题目链接 题意： # 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： # 暴力即可orz(数据是真的水啊。

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

题目链接 题意：定义一个函数 F。 For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12) Its continuous sequences are: (1, 4) (4, 7) (9, 12) (1, 4), (4, 7) (4, 7), (9, 12) (1, 4), (4, 7), (9, 12) 二分。 题目描述得很烂，看例子吧，大概就是：如果字符串 y 在字符串 x 中出现 n 次，那么 F(x,y)=n*(n+1)/2

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

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月21日 星期六 14时44分39秒 4File Name :code/zoj/3195.cpp 5************************************************ */ 6 7 8 9#include <cstdio> 10#include <cstring> 11#include <iostream> 12#include <algorithm> 13#include <vector> 14#include <queue> 15#include <set> 16#include <map> 17#include <string> 18#include <cmath> 19#include <cstdlib> 20#include <ctime> 21#define fst first 22#define sec second 23#define lson l,m,rt<<1 24#define rson m+1,r,rt<<1|1 25#define ms(a,x) memset(a,x,sizeof(a)) 26typedef long long LL; 27#define pi pair < int ,int > 28#define MP make_pair 29 30using namespace std; 31const double eps = 1E-8; 32const int dx4[4]={1,0,0,-1}; 33const int dy4[4]={0,-1,1,0}; 34const int inf = 0x3f3f3f3f; 35const int N=5E4+7; 36int n,m; 37vector < pi > edge[N]; 38int q; 39int in[N]; 40int E[2*N],R[2*N],dis[N],depth[2*N]; 41int p; 42int dp[2*N][20]; 43void dfs( int u,int dep,int d,int pre) 44{ 45 46 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl; 47 p++; 48 E[p] = u; 49 depth[p] = dep; 50 R[u] = p ; 51 dis[u] = d; 52 53 54 int siz = edge[u].size(); 55 for ( int i = 0 ; i < siz ; i++) 56 { 57 int v = edge[u][i].fst; 58 if (v==pre) continue; 59 dfs(v,dep+1,d+edge[u][i].sec,u); 60 61 p++; 62 E[p] = u; 63 depth[p] = dep; 64 } 65} 66 67 68 69int _min( int l,int r) 70{ 71 if (depth[l]<depth[r]) return l; 72 return r; 73} 74void rmq_init() 75{ 76 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i; 77 78 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 79 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 80 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 81} 82 83int rmq_min( int l,int r) 84{ 85 if (l>r) swap(l,r); 86 int k = 0 ; 87 while (1<<(k+1)<=r-l+1) k++; 88 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 89} 90int solve (int x,int y) 91{ 92 int LCA = E[rmq_min(R[x],R[y])]; 93 int res = dis[x] + dis[y] - 2 * dis[LCA]; 94 return res; 95} 96int main() 97{ 98 #ifndef ONLINE_JUDGE 99 freopen("code/in.txt","r",stdin); 100 #endif 101 102 ms(in,0); 103 bool ok = false; 104 while (~scanf("%d",&n)){ 105 if (ok) puts(""); 106 ok = true; 107 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 108 for ( int i = 1 ; i <= n-1 ; i++) 109 { 110 int u,v,w; 111 scanf("%d%d%d",&u,&v,&w); 112 edge[u].push_back(make_pair(v,w)); 113 edge[v].push_back(make_pair(u,w)); 114 } 115 116 117 p = 0 ; 118 dfs(0,0,0,-1); 119 rmq_init(); 120 121 scanf("%d",&q); 122 while (q--) 123 { 124 int x,y,z; 125 scanf("%d%d%d",&x,&y,&z); 126 int ans = solve(x,y)+solve(x,z)+solve(y,z); 127 printf("%d\n",ans/2); 128 } 129 } 130 131#ifndef ONLINE_JUDGE 132 fclose(stdin); 133#endif 134 return 0; 135}

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. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 16时52分03秒 4File Name :code/hdu/3530.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n; 35int a[N]; 36int dp[N][20],dp2[N][20]; 37int m,k; 38 39void rmq_init() 40{ 41 for ( int i = 1 ; i <= n ; i ++) 42 dp[i][0] = dp2[i][0] = a[i]; 43 44 for ( int j = 1 ; (1<<j) <= n ; j++) 45 for ( int i = 1 ; i + (1<<j) -1 <= n ; i++) 46 { 47 dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 48 dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]); 49 } 50} 51 52int rmq( int l,int r) 53{ 54 int k = 0 ; 55 while (1<<(k+1)<=r-l+1) k++; 56 int mx = max(dp[l][k],dp[r-(1<<k)+1][k]); 57 int mn = min(dp2[l][k],dp2[r-(1<<k)+1][k]); 58 59 return mx-mn; 60} 61 62int ruler() 63{ 64 int head = 1; 65 int tail = 1; 66 int res = -1 ; 67 while (tail<=n) 68 { 69 int cur = rmq(head,tail); 70 while (head<tail&&rmq(head,tail)>k) head++; 71 while (tail<n&&rmq(head,tail)<m) tail++; 72 //if (tail>n) break; 73 cur = rmq(head,tail); 74 if (cur>=m&&cur<=k) 75 { 76 res = max(res,tail-head); 77 } 78// cout<<"head:"<<head<<" tail:"<<tail<<" cur:"<<cur<<" res:"<<res<<endl; 79 tail++; 80 81 } 82 return res+1; 83} 84int main() 85{ 86 #ifndef ONLINE_JUDGE 87 freopen("code/in.txt","r",stdin); 88 #endif 89 90 while (scanf("%d %d %d",&n,&m,&k)!=EOF) 91 { 92 ms(dp,0); 93 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 94 if (m>k) 95 { 96 puts("0"); 97 continue; 98 } 99 rmq_init(); 100 printf("%d\n",ruler()); 101 } 102 103 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 15时44分12秒 4File Name :code/poj/1470.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=905; 34int n; 35vector <int> edge[N]; 36int in[N]; 37int E[2*N],R[2*N]; 38int depth[2*N]; 39int p; 40int dp[2*N][12]; 41int cnt[N]; 42void dfs( int u,int dep) 43{ 44 p++; 45 E[p] = u ; 46 depth[p] = dep; 47 R[u] = p; 48 int siz = edge[u].size(); 49 for ( int i = 0 ; i < siz ; i ++) 50 { 51 int v = edge[u][i]; 52 53 dfs(v,dep+1); 54 p++; 55 E[p] = u; 56 depth[p] = dep; 57 } 58} 59 60int _min( int l,int r) 61{ 62 if (depth[l]<depth[r]) return l; 63 return r; 64} 65void rmq_init() 66{ 67 for ( int i = 1 ; i <=2*n+2 ; i++) dp[i][0] = i; 68 69 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 70 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 71 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 72} 73 74int rmq_min( int l,int r) 75{ 76 if (l>r) swap(l,r); 77 int k = 0; 78 while (1<<(k+1) <= r-l+1) k++; 79 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 while (scanf("%d",&n)!=EOF) 88 { 89 ms(in,0); 90 for ( int i = 1 ; i <= n ; i++) edge[i].clear(); 91 for ( int i = 1 ; i <= n ; i++) 92 { 93 char ch[5]; 94 int x,num; 95 scanf("%d%2s%d%1s",&x,ch,&num,ch); 96// cout<<"x:"<<x<<" num:"<<num<<endl; 97 98 for ( int i = 1 ; i <= num ; i++) 99 { 100 int y; 101 scanf("%d",&y); 102 edge[x].push_back(y); 103 in[y]++; 104// cout<<"y:"<<y<<endl; 105 } 106 } 107 108 int root ; 109 for ( int i = 1 ; i <= n ; i++) if (in[i]==0) root = i ; 110// cout<<"root:"<<root<<endl; 111 p = 0; 112 dfs(root,0); 113 rmq_init(); 114 115 ms(cnt,0); 116 117 int q; 118 scanf("%d",&q); 119// cout<<"q:"<<q<<endl; 120 while (q--) 121 { 122 char ch[5]; 123 int x,y; 124 scanf("%1s%d%d%1s",ch,&x,&y,ch); 125 int LCA = E[rmq_min(R[x],R[y])]; 126// cout<<"x:"<<x<<" y:"<<y<<" LCA:"<<LCA<<endl; 127 cnt[LCA]++; 128 } 129// cout<<"n:"<<n<<endl; 130 for ( int i = 1 ; i <= n ; i++) 131 { 132// cout<<"cnt[i]:"<<cnt[i]<<endl; 133 if (cnt[i]==0) continue; 134 printf("%d:%d\n",i,cnt[i]); 135 } 136 } 137 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。

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

poj 3368 题目链接 题意：给出n个非减的数a[i]，求区间[l,r]中出现次数最多的数的出现的次数。 思路：由于数列非减，那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i]，表示从当前位置向左边延伸最多延伸几个相等的数。

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现== 转载一篇题解：poj2452解题报告

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle… 很容易发现，由于是方阵，长宽是相等的，所以有一维是可以省略的。 也就是所谓的降维？

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。 思路：二维rmq.同时用到最大值和最小值的话可以把初始化写在一起。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月16日 星期一 18时31分23秒 4File Name :code/poj/2019.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=251; 34int a[N][N]; 35int dp[N][N][8][8]; 36int dp2[N][N][8][8]; 37int n,b,q; 38 39void init_rmq() 40{ 41 for ( int i = 1 ;i <= n ; i++) 42 for ( int j = 1 ; j <= n ; j++) 43 dp[i][j][0][0] = dp2[i][j][0][0] = a[i][j]; 44 45 46 for ( int i = 0 ; (1<<i)<= n ; i++) 47 for ( int j = 0 ; (1<<j) <= n ; j++) 48 if (i==0 && j==0) continue; 49 else for ( int p = 1 ; p + (1<<i)-1 <= n ; p++) 50 for ( int q = 1 ; q + (1<<j)-1 <= n ; q++) 51 if (i==0) 52 { 53 dp[p][q][i][j] = max(dp[p][q][i][j-1],dp[p][q+(1<<(j-1))][i][j-1]); 54 dp2[p][q][i][j] = min(dp2[p][q][i][j-1],dp2[p][q+(1<<(j-1))][i][j-1]); 55 } 56 else 57 { 58 dp[p][q][i][j] = max(dp[p][q][i-1][j],dp[p+(1<<(i-1))][q][i-1][j]); 59 dp2[p][q][i][j] = min(dp2[p][q][i-1][j],dp2[p+(1<<(i-1))][q][i-1][j]); 60 } 61} 62 63 64int _rmq(int x1,int y1,int x2,int y2) 65{ 66 int k1 = 0 ; 67 int k2 = 0 ; 68 while (1<<(k1+1)<=x2-x1+1) k1++; 69 while (1<<(k2+1)<=y2-y1+1) k2++; 70 71 int tmp1 = dp[x1][y1][k1][k2]; 72 int tmp2 = dp[x2-(1<<k1)+1][y1][k1][k2]; 73 int tmp3 = dp[x1][y2-(1<<k2)+1][k1][k2]; 74 int tmp4 = dp[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2]; 75 76 int mx = max(max(tmp1,tmp2),max(tmp3,tmp4)); 77 78 tmp1 = dp2[x1][y1][k1][k2]; 79 tmp2 = dp2[x2-(1<<k1)+1][y1][k1][k2]; 80 tmp3 = dp2[x1][y2-(1<<k2)+1][k1][k2]; 81 tmp4 = dp2[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2]; 82 83 int mn = min(min(tmp1,tmp2),min(tmp3,tmp4)); 84 85 // cout<<"mx:"<<mx<<" mn:"<<mn<<endl; 86 87 return mx - mn; 88} 89 90 91int main() 92{ 93 #ifndef ONLINE_JUDGE 94 freopen("code/in.txt","r",stdin); 95 #endif 96 scanf("%d %d %d",&n,&b,&q); 97 for ( int i = 1 ; i <= n ; i++) 98 for ( int j = 1 ; j <= n ; j++) scanf("%d",&a[i][j]); 99 init_rmq(); 100 101 while (q--) 102 { 103 int x1,y1; 104 scanf("%d %d",&x1,&y1); 105 printf("%d\n",_rmq(x1,y1,x1+b-1,y1+b-1)); 106 } 107 108 109 110 #ifndef ONLINE_JUDGE 111 fclose(stdin); 112 #endif 113 return 0; 114}

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

1636: [Usaco2007 Jan]Balanced Lineup # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss] Description # For the daily milking, Farmer John’s N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height. Farmer John has made a list of Q (1 <= Q <= 200,000) potential groups of cows and their heights (1 <= height <= 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.