peltorator

Disjoint Sparse Table: простейший вариант

Feb 17th, 2021 (edited)
586
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. pair<int, int> accumulatingFunction(pair<int, int> left, pair<int, int> right) {
  6.     if (left.first > right.first) {
  7.         return left;
  8.     } else if (left.first < right.first) {
  9.         return right;
  10.     } else {
  11.         return {left.first, left.second + right.second};
  12.     }
  13. }
  14.  
  15. const int LOG = 20;
  16. const int MAXN = (1 << LOG);
  17.  
  18. pair<int, int> sparseTable[LOG][MAXN]; // first -- max, second -- cnt
  19. int highestBit[MAXN];
  20.  
  21. void build(vector<int> arr) {
  22.     int height = 0;
  23.     int extendedSize = 1;
  24.     int n = arr.size();
  25.     while (extendedSize <= n) {
  26.         extendedSize *= 2;
  27.         height++;
  28.     }
  29.     highestBit[1] = 0;
  30.     for (int i = 2; i < extendedSize; i++) {
  31.         highestBit[i] = highestBit[i >> 1] + 1;
  32.     }
  33.     arr.resize(extendedSize, -1);
  34.  
  35.     for (int lvl = 0; lvl < height; lvl++) {
  36.         int curLen = (1 << lvl);
  37.         for (int center = curLen; center < extendedSize; center += 2 * curLen) {
  38.             pair<int,int> prefAccum = {-1, 0}; // neutral element
  39.             for (int i = center; i < center + curLen; i++) {
  40.                 sparseTable[lvl][i] = prefAccum;
  41.                 prefAccum = accumulatingFunction(prefAccum, {arr[i], 1});
  42.             }
  43.             for (int i = center - 1; i >= center - curLen; i--) {
  44.                 sparseTable[lvl][i] = accumulatingFunction({arr[i], 1}, sparseTable[lvl][i + 1]);
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50. pair<int, int> query(int left, int right) { // [left, right)
  51.     int lvl = highestBit[left ^ right];
  52.     return accumulatingFunction(sparseTable[lvl][left], sparseTable[lvl][right]);
  53. }
  54.  
  55. int main() {
  56.     int n;
  57.     cin >> n;
  58.     vector<int> arr(n);
  59.     for (int i = 0; i < n; i++) {
  60.         cin >> arr[i];
  61.     }
  62.     build(arr);
  63.  
  64.     int queriesNumber;
  65.     cin >> queriesNumber;
  66.     for (int i = 0; i < queriesNumber; i++) {
  67.         int left, right;
  68.         cin >> left >> right;
  69.         left--;
  70.         pair<int, int> result = query(left, right);
  71.         cout << result.first << ' ' << result.second << '\n';
  72.     }
  73.     return 0;
  74. }
  75.  
RAW Paste Data