首页 > 代码库 > hdu 2586 + hdu 4123(RMQ算法与LCA）
hdu 2586 + hdu 4123(RMQ算法与LCA）
转自：http://blog.csdn.net/liang5630/article/details/7917702
rmq算法可用来求区间最值，区间最值差，树上最近公共祖先，时间复杂度O（nlogn）
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题，下面介绍一下解决这两种问题的比较高效的算法。当然，该问题也可以用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)，这里我们暂不介绍。
2.RMQ算法
对于该问题，最容易想到的解决方案是遍历，复杂度是O(n)。但当数据量非常大且查询很频繁时，该算法无法在有效的时间内查询出正解。
本节介绍了一种比较高效的在线算法（ST算法）解决这个问题。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。
（一）首先是预处理，用动态规划（DP）解决。
设A[i]是要求区间最值的数列，F[i, j]表示从第i个数起连续2^j个数中的最大值。（DP的状态）
例如：
A数列为：3 2 4 5 6 8 1 2 9 7
F[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。同理 F[1,1] = max(3,2) = 3, F[1，2]=max(3,2,4,5) = 5，F[1，3] = max(3,2,4,5,6,8,1,2) = 8;
并且我们可以容易的看出F[i,0]就等于A[i]。（DP的初始值）
这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。
模版：
1 void init(int n) 2 { 3 // f[i,j]表示[i,i+2^j-1]区间最大值 4 // f[i,j]=max(d[i,j-1], d[i+2^(j-1),j-1]) 5 for (int i = 1; i <= n; ++i) f2[i][0] = f1[i][0] = ans[i]; 6 for (int j = 1; (1<<j) <= n; ++j) 7 for (int i = 1; i+(1<<j)-1 <= n; ++i) { 8 f1[i][j] = max(f1[i][j-1], f1[i+(1<<j-1)][j-1]); 9 f2[i][j] = min(f2[i][j-1], f2[i+(1<<j-1)][j-1]);10 }11 }
我们把F[i，j]平均分成两段（因为f[i，j]一定是偶数个数字），从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i，j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）。
这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？可以是i在外，j在内吗？
答案是不可以。因为我们需要理解这个状态转移方程的意义。
状态转移方程的含义是：先更新所有长度为F[i,0]即1个元素，然后通过2个1个元素的最值，获得所有长度为F[i,1]即2个元素的最值，然后再通过2个2个元素的最值，获得所有长度为F[i,2]即4个元素的最值，以此类推更新所有长度的最值。
而如果是i在外，j在内的话，我们更新的顺序就是F[1,0],F[1,1],F[1,2],F[1,3],表示更新从1开始1个元素，2个元素，4个元素，8个元素（A[0],A[1],....A[7]）的最值，这里F[1,3] = max(max(A[0],A[1],A[2],A[3]),max(A[4],A[5],A[6],A[7]))的值，但是我们根本没有计算max(A[0],A[1],A[2],A[3])和max(A[4],A[5],A[6],A[7])，所以这样的方法肯定是错误的。
为了避免这样的错误，一定要好好理解这个状态转移方程所代表的含义。
（二）然后是查询。
假如我们需要查询的区间为(i,j)，那么我们需要找到覆盖这个闭区间(左边界取i，右边界取j)的最小幂（可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789）。
因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1)，则有：RMQ(A, i, j)=max{F[i , k], F[ j - 2 ^ k + 1, k]}。
举例说明，要求区间[2，8]的最大值，k = log2（8 - 2 + 1）= 2，即求max(F[2, 2]，F[8 - 2 ^ 2 + 1, 2]) = max(F[2, 2]，F[5, 2])；
在这里我们也需要注意一个地方，就是<<运算符和+-运算符的优先级。
比如这个表达式：5 - 1 << 2是多少？
答案是：4 * 2 * 2 = 16。所以我们要写成5 - (1 << 2)才是5-1 * 2 * 2 = 1。
3.LCA:也就是对树排一个DFS序，在pos[u],和pos[v]区间内最小值一定是其最近公共祖先
HDU2586：
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #include <iostream> 6 #include <map> 7 #include <queue> 8 #include <stack> 9 #include <cmath>10 //#pragma comment(linker, "/STACK:102400000,102400000")11 using namespace std;12 #define PF(x) cout << "debug: " << x << " ";13 #define EL cout << endl;14 #define PC(x) puts(x);15 typedef long long ll;16 #define CLR(x, v) sizeof (x, v, sizeof(x))17 using namespace std;18 const int INF = 0x5f5f5f5f;19 const int N= 2e5 + 10;20 const int mod=1e9 + 7;21 const int maxn = 4e4 + 10;22 int t,n,m,ans[maxn],cnt,f[maxn][20];23 vector<pair <int,int> >gra[maxn];24 void dfs(int u,int fa){25 26 for(int i = 0;i < gra[u].size();i++){27 int v = gra[u][i].first;28 if(v == fa) continue;29 ans[v] = ans[u] + gra[u][i].second;30 dfs(v,u);31 }32 }33 void init(){34 for(int i = 1;i <= n;i++) f[i][0] = ans[i];35 for(int j = 1;(1<<j) <= n;j++)36 for(int i = 1;i + (1<<j) - 1 <= n;i++)37 f[i][j] = min(f[i][j-1],f[i+(1<<j-1)][j-1]);38 }39 int query(int l, int r)40 {41 int k = 0;42 while (1<<k+1 <= r-l+1) ++k;43 return min(f[l][k], f[r-(1<<k)+1][k]);44 }45 int main()46 {47 // freopen("in.txt","r",stdin);48 cin>>t;49 while(t--){50 scanf("%d%d",&n,&m);51 // cout<<n<<" "<<m<<endl;52 int a,b,c;53 for(int i = 1;i <= n;i++)54 gra[i].clear();55 for(int i = 1;i < n;i++){56 scanf("%d%d%d",&a,&b,&c);57 // cout<<a<<" "<<b<<" "<<c<<endl;58 gra[a].push_back(make_pair(b,c));59 gra[b].push_back(make_pair(a,c));60 }61 cnt = 0;62 dfs(1,-1);63 init();64 //cout<<m<<endl;65 while(m--){66 scanf("%d%d",&a,&b);67 68 //cout<<a<<" "<<b<<endl;69 if(a > b) swap(a,b);70 int num = query(a,b);71 cout<<ans[a] - num + ans[b] - num<<endl;72 73 }74 }75 return 0;76 }
HDU4123：
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #include <iostream> 6 #include <map> 7 #include <queue> 8 #include <stack> 9 #include <cmath> 10 //#pragma comment(linker, "/STACK:102400000,102400000") 11 using namespace std; 12 #define PF(x) cout << "debug: " << x << " "; 13 #define EL cout << endl; 14 #define PC(x) puts(x); 15 typedef long long ll; 16 #define CLR(x, v) sizeof (x, v, sizeof(x)) 17 using namespace std; 18 const int INF = 0x5f5f5f5f; 19 const int N= 2e5 + 10; 20 const int mod=1e9 + 7; 21 const int maxn = 5e4 + 10; 22 int n,m,dp1[maxn],dp2[maxn],ans[maxn],maxp[maxn]; 23 vector< pair<int,int> > gra[maxn]; 24 void dfs1(int u,int fa){ 25 dp1[u] = dp2[u] = 0; 26 for(int i = 0;i < gra[u].size();i++){ 27 int v = gra[u][i].first; 28 if(v == fa) continue; 29 dfs1(v,u); 30 if(dp1[u] < dp1[v] + gra[u][i].second){ 31 dp1[u] = dp1[v] + gra[u][i].second; 32 maxp[u] = v; 33 } 34 } 35 } 36 void dfs2(int u,int fa){ 37 for(int i = 0;i < gra[u].size();i++){ 38 int v = gra[u][i].first; 39 if(v == fa) continue; 40 if(v != maxp[u]){ 41 dp2[v] = max(dp2[v],dp1[u] + gra[u][i].second); 42 dp2[v] = max(dp2[v],dp2[u] + gra[u][i].second); 43 } 44 else{ 45 for(int j = 0;j < gra[u].size();j++){ 46 int v1 = gra[u][j].first; 47 if(v1 == fa||v1 == v||v1 == maxp[u]) continue; 48 dp2[v] = max(dp2[v],dp1[v1] + gra[u][i].second + gra[u][j].second); 49 } 50 dp2[v] = max(dp2[v],dp2[u] + gra[u][i].second); 51 } 52 dfs2(v, u);/// 53 } 54 55 } 56 int f1[N][20], f2[N][20]; 57 void init(int n) 58 { 59 // f[i,j]表示[i,i+2^j-1]区间最大值 60 // f[i,j]=max(d[i,j-1], d[i+2^(j-1),j-1]) 61 for (int i = 1; i <= n; ++i) f2[i][0] = f1[i][0] = ans[i]; 62 for (int j = 1; (1<<j) <= n; ++j) 63 for (int i = 1; i+j-1 <= n; ++i) { 64 f1[i][j] = max(f1[i][j-1], f1[i+(1<<j-1)][j-1]); 65 f2[i][j] = min(f2[i][j-1], f2[i+(1<<j-1)][j-1]); 66 } 67 } 68 69 int query(int l, int r) 70 { 71 int k = 0; 72 while (1<<k+1 <= r-l+1) ++k; 73 return max(f1[l][k], f1[r-(1<<k)+1][k]) - min(f2[l][k], f2[r-(1<<k)+1][k]); 74 } 75 76 int main() 77 { 78 // freopen("in.txt","r",stdin); 79 while(scanf("%d%d",&n,&m)){ 80 if(n == 0&&n == m) 81 break; 82 int x,y,z; 83 for(int i = 1;i <= n;i++) 84 gra[i].clear(); 85 for(int i = 1;i < n;i++){ 86 scanf("%d%d%d",&x,&y,&z); 87 gra[x].push_back(make_pair(y,z)); 88 gra[y].push_back(make_pair(x,z)); 89 } 90 dfs1(1,-1); 91 dfs2(1,-1); 92 for(int i = 1;i <= n;i++) 93 ans[i] = max(dp1[i],dp2[i]); 94 95 //for (int i = 1; i <= n; ++i) printf("%d:%d %d %d\n", i, dp1[i], dp2[i], ans[i]); 96 97 init(n); 98 while (m--) { 99 int q; scanf("%d", &q);100 int r = 1;101 int res = 0;102 for (int i = 1; i <= n; ++i) {103 while (r <= n && query(i, r) <= q) r++;104 res = max(res, r-i);105 }106 printf("%d\n", res);107 }108 }109 return 0;110 }
hdu 2586 + hdu 4123(RMQ算法与LCA）