Advertisement
Guest User

LCA com sparse Table

a guest
Jun 28th, 2016
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. struct LCA{
  2.    
  3.     LCA(){
  4.         build();
  5.     }
  6.  
  7.     void build(){
  8.         int base = 1;
  9.         int pot = 0;
  10.         for(int i = 0; i < 2*MAXN; i++){
  11.             if(i >= base * 2){
  12.                 pot++;
  13.                 base *= 2;
  14.             }
  15.             pre[i] = pot;
  16.             dp[i][0] = i;
  17.         }
  18.         base = 2;
  19.         pot = 1;
  20.         while(base <= 2*n){
  21.             for(int i = 0; i + base / 2 < 2*n; i++){
  22.                 int before = base / 2;
  23.                 if(L[dp[i][pot-1]] < L[dp[i + before][pot-1]]){
  24.                     dp[i][pot] = dp[i][pot-1];
  25.                 }else{
  26.                     dp[i][pot] = dp[i + before][pot-1];
  27.                 }
  28.             }
  29.             base *= 2;
  30.             pot++;
  31.         }
  32.     }
  33.  
  34.     int getLca(int u, int v){
  35.         int l = H[u];
  36.         int r = H[v];
  37.         if(l > r){
  38.             swap(l,r);
  39.         }
  40.         int len = r-l+1;
  41.         if(len == 1){
  42.             return E[dp[r][0]];
  43.         }else{
  44.             int base = (1 << pre[len]);
  45.             int pot = pre[len];
  46.             if(L[dp[l][pot]] < L[dp[r-base+1][pot]]){
  47.                 return E[dp[l][pot]];
  48.             }else{
  49.                 return E[dp[r-base+1][pot]];
  50.             }
  51.         }
  52.     }
  53.  
  54. };
  55.  
  56. void dfs(int x, int depth){
  57.     vis[x] = 1;
  58.     if(H[x] == -1) H[x] = idx;
  59.     L[idx] = depth;
  60.     E[idx++] = x;
  61.     for(int i = 0; i < g[x].size(); i++){
  62.         int next = g[x][i].first;
  63.         int cost = g[x][i].second;
  64.         if(!vis[next]){
  65.             dfs(next, depth+1);
  66.             L[idx] = depth;
  67.             E[idx++] = x;
  68.         }
  69.     }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement