Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Add Comment
Please, Sign In to add comment