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

#include <bits/stdc++.h>

using namespace std;

pair<int, int> accumulatingFunction(pair<int, int> left, pair<int, int> right) {
    if (left.first > right.first) {
        return left;
    } else if (left.first < right.first) {
        return right;
    } else {
        return {left.first, left.second + right.second};
    }
}

const int LOG = 20;
const int MAXN = (1 << LOG);

pair<int, int> sparseTable[LOG][MAXN]; // first -- max, second -- cnt
int highestBit[MAXN];

void build(vector<int> arr) {
    int height = 0;
    int extendedSize = 1;
    int n = arr.size();
    while (extendedSize <= n) {
        extendedSize *= 2;
        height++;
    }
    highestBit[1] = 0;
    for (int i = 2; i < extendedSize; i++) {
        highestBit[i] = highestBit[i >> 1] + 1;
    }
    arr.resize(extendedSize, -1);

    for (int lvl = 0; lvl < height; lvl++) {
        int curLen = (1 << lvl);
        for (int center = curLen; center < extendedSize; center += 2 * curLen) {
            pair<int,int> prefAccum = {-1, 0}; // neutral element
            for (int i = center; i < center + curLen; i++) {
                sparseTable[lvl][i] = prefAccum;
                prefAccum = accumulatingFunction(prefAccum, {arr[i], 1});
            }
            for (int i = center - 1; i >= center - curLen; i--) {
                sparseTable[lvl][i] = accumulatingFunction({arr[i], 1}, sparseTable[lvl][i + 1]);
            }
        }
    }
}

pair<int, int> query(int left, int right) { // [left, right)
    int lvl = highestBit[left ^ right];
    return accumulatingFunction(sparseTable[lvl][left], sparseTable[lvl][right]);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    build(arr);

    int queriesNumber;
    cin >> queriesNumber;
    for (int i = 0; i < queriesNumber; i++) {
        int left, right;
        cin >> left >> right;
        left--;
        pair<int, int> result = query(left, right);
        cout << result.first << ' ' << result.second << '\n';
    }
    return 0;
}