peltorator

Disjoint Sparse Table: версия с шаблонами

Feb 17th, 2021 (edited)
690
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. struct MaxCntAccumulator {
  6.     int segmentMax;
  7.     int maxCnt;
  8.  
  9.     MaxCntAccumulator() // neutral element
  10.         : segmentMax(-1), maxCnt(0) {}
  11.  
  12.     MaxCntAccumulator(int arrayElem) // from a single value
  13.         : segmentMax(arrayElem), maxCnt(1) {}
  14.  
  15.     MaxCntAccumulator(int segmentMax, int maxCnt)
  16.         : segmentMax(segmentMax), maxCnt(maxCnt) {}
  17.  
  18.     MaxCntAccumulator operator+(const MaxCntAccumulator &other) { // accumulating function
  19.         if (segmentMax > other.segmentMax) {
  20.             return *this;
  21.         } else if (segmentMax < other.segmentMax) {
  22.             return other;
  23.         } else {
  24.             return MaxCntAccumulator(segmentMax, maxCnt + other.maxCnt);
  25.         }
  26.     }
  27. };
  28.  
  29. template<typename AccumType>
  30. struct DisjointSparseTable {
  31.     static const int LOG = 20;
  32.     static const int MAXN = (1 << LOG);
  33.  
  34.     AccumType sparseTable[LOG][MAXN];
  35.  
  36.     template<typename InputType>
  37.     DisjointSparseTable(const vector<InputType> &arr) {
  38.         int n = arr.size();
  39.         int height = highestBit(n) + 1;
  40.         int extendedSize = (1 << height);
  41.  
  42.         for (int lvl = 0; lvl < height; lvl++) {
  43.             int curLen = (1 << lvl);
  44.             for (int center = curLen; center < extendedSize; center += 2 * curLen) {
  45.                 sparseTable[lvl][center] = AccumType();
  46.                 for (int i = center + 1; i < center + curLen; i++) {
  47.                     sparseTable[lvl][i] = sparseTable[lvl][i - 1] + (i < n ? AccumType(arr[i]) : AccumType());
  48.                 }
  49.                 for (int i = center - 1; i >= center - curLen; i--) {
  50.                     sparseTable[lvl][i] = (i < n ? AccumType(arr[i]) : AccumType()) + sparseTable[lvl][i + 1];
  51.                 }
  52.             }
  53.         }
  54.     }
  55.  
  56.     int highestBit(int number) {
  57.         return 31 - __builtin_clz(number);
  58.     }
  59.  
  60.     AccumType query(int left, int right) { // [left, right)
  61.         int lvl = highestBit(left ^ right);
  62.         return sparseTable[lvl][left] + sparseTable[lvl][right];
  63.     }
  64. };
  65.  
  66.  
  67. int main() {
  68.     int n;
  69.     cin >> n;
  70.     vector<int> arr(n);
  71.     for (int &elem : arr) {
  72.         cin >> elem;
  73.     }
  74.     DisjointSparseTable<MaxCntAccumulator> maxCntSparse(arr);
  75.  
  76.     int queriesNumber;
  77.     cin >> queriesNumber;
  78.     for (int i = 0; i < queriesNumber; i++) {
  79.         int left, right;
  80.         cin >> left >> right;
  81.         left--;
  82.         MaxCntAccumulator result = maxCntSparse.query(left, right);
  83.         cout << result.segmentMax << ' ' << result.maxCnt << '\n';
  84.     }
  85.     return 0;
  86. }
  87.  
RAW Paste Data