daily pastebin goal
92%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Sparse_table
  2. {
  3.     vector < int > f;
  4.     vector < vector < int > > t, pr;
  5.     int sz, n;
  6.    
  7.     Sparse_table() {}
  8.     Sparse_table(vector < int > & a, vector < int > & b)
  9.     {
  10.         n = (int)a.size();
  11.         sz = log2(n) + 1;
  12.         f.resize(n + 1);
  13.         pr = vector < vector < int > > (sz, vector < int > (n));
  14.         t = vector < vector < int > > (sz, vector < int > (n));
  15.         f[1] = 0;
  16.         for (int i = 2; i <= n; i++)
  17.             f[i] = f[i / 2] + 1;
  18.         for (int i = 0; i < n; i++)
  19.         {
  20.             t[0][i] = a[i];
  21.             pr[0][i] = b[i];
  22.         }
  23.         for (int j = 1; j < sz; j++)
  24.         {
  25.             for (int i = 0; i + (1 << j) < n; i++)
  26.             {
  27.                 if (t[j - 1][i] < t[j - 1][i + (1 << (j - 1))])
  28.                 {
  29.                     t[j][i] = t[j - 1][i];
  30.                     pr[j][i] = pr[j - 1][i];
  31.                 }
  32.                 else
  33.                 {
  34.                     t[j][i] = t[j - 1][i + (1 << (j - 1))];
  35.                     pr[j][i] = pr[j - 1][i + (1 << (j - 1))];
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     int get(int l, int r)
  41.     {
  42.         if (l > r)
  43.             swap(l, r);
  44.         int len = r - l + 1, res;
  45.         if (t[f[len]][l] < t[f[len]][r - (1 << f[len]) + 1])
  46.             res = pr[f[len]][l];
  47.         else
  48.             res = pr[f[len]][r - (1 << f[len]) + 1];
  49.         return res;        
  50.     }
  51. };
RAW Paste Data
Top