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

Feb 17th, 2021 (edited)
1,598
0
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.