Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Sparse_table
- {
- vector < int > f;
- vector < vector < int > > t, pr;
- int sz, n;
- Sparse_table() {}
- Sparse_table(vector < int > & a, vector < int > & b)
- {
- n = (int)a.size();
- sz = log2(n) + 1;
- f.resize(n + 1);
- pr = vector < vector < int > > (sz, vector < int > (n));
- t = vector < vector < int > > (sz, vector < int > (n));
- f[1] = 0;
- for (int i = 2; i <= n; i++)
- f[i] = f[i / 2] + 1;
- for (int i = 0; i < n; i++)
- {
- t[0][i] = a[i];
- pr[0][i] = b[i];
- }
- for (int j = 1; j < sz; j++)
- {
- for (int i = 0; i + (1 << j) < n; i++)
- {
- if (t[j - 1][i] < t[j - 1][i + (1 << (j - 1))])
- {
- t[j][i] = t[j - 1][i];
- pr[j][i] = pr[j - 1][i];
- }
- else
- {
- t[j][i] = t[j - 1][i + (1 << (j - 1))];
- pr[j][i] = pr[j - 1][i + (1 << (j - 1))];
- }
- }
- }
- }
- int get(int l, int r)
- {
- if (l > r)
- swap(l, r);
- int len = r - l + 1, res;
- if (t[f[len]][l] < t[f[len]][r - (1 << f[len]) + 1])
- res = pr[f[len]][l];
- else
- res = pr[f[len]][r - (1 << f[len]) + 1];
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement