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

#include <bits/stdc++.h>

using namespace std;

struct MaxCntAccumulator {
    int segmentMax;
    int maxCnt;

    MaxCntAccumulator() // neutral element
        : segmentMax(-1), maxCnt(0) {}

    MaxCntAccumulator(int arrayElem) // from a single value
        : segmentMax(arrayElem), maxCnt(1) {}

    MaxCntAccumulator(int segmentMax, int maxCnt)
        : segmentMax(segmentMax), maxCnt(maxCnt) {}

    MaxCntAccumulator operator+(const MaxCntAccumulator &other) { // accumulating function
        if (segmentMax > other.segmentMax) {
            return *this;
        } else if (segmentMax < other.segmentMax) {
            return other;
        } else {
            return MaxCntAccumulator(segmentMax, maxCnt + other.maxCnt);
        }
    }
};

template<typename AccumType>
struct DisjointSparseTable {
    static const int LOG = 20;
    static const int MAXN = (1 << LOG);

    AccumType sparseTable[LOG][MAXN];

    template<typename InputType>
    DisjointSparseTable(const vector<InputType> &arr) {
        int n = arr.size();
        int height = highestBit(n) + 1;
        int extendedSize = (1 << height);

        for (int lvl = 0; lvl < height; lvl++) {
            int curLen = (1 << lvl);
            for (int center = curLen; center < extendedSize; center += 2 * curLen) {
                sparseTable[lvl][center] = AccumType();
                for (int i = center + 1; i < center + curLen; i++) {
                    sparseTable[lvl][i] = sparseTable[lvl][i - 1] + (i < n ? AccumType(arr[i]) : AccumType());
                }
                for (int i = center - 1; i >= center - curLen; i--) {
                    sparseTable[lvl][i] = (i < n ? AccumType(arr[i]) : AccumType()) + sparseTable[lvl][i + 1];
                }
            }
        }
    }

    int highestBit(int number) {
        return 31 - __builtin_clz(number);
    }

    AccumType query(int left, int right) { // [left, right)
        int lvl = highestBit(left ^ right);
        return sparseTable[lvl][left] + sparseTable[lvl][right];
    }
};


int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int &elem : arr) {
        cin >> elem;
    }
    DisjointSparseTable<MaxCntAccumulator> maxCntSparse(arr);

    int queriesNumber;
    cin >> queriesNumber;
    for (int i = 0; i < queriesNumber; i++) {
        int left, right;
        cin >> left >> right;
        left--;
        MaxCntAccumulator result = maxCntSparse.query(left, right);
        cout << result.segmentMax << ' ' << result.maxCnt << '\n';
    }
    return 0;
}