Overview

This problem asks us to efficiently determine, for each query, the number of mountains that are “visible” when viewing a given mountain range over a specific interval \([L_j, R_j]\) from the left (west).

A mountain is visible if “there is no mountain strictly taller than it to its left (within the interval).” This is equivalent to counting the mountains that update (or maintain) the “maximum elevation seen so far” when scanning from left to right.

---

Analysis

1. Brute Force Approach and Its Limitations

For each query \([L_j, R_j]\), one could scan from the left endpoint \(L_j\) to the right endpoint \(R_j\), maintaining the maximum elevation encountered so far and counting visible mountains. However, this method takes \(O(N)\) time per query in the worst case. With \(Q\) queries, the total time complexity is \(O(NQ)\), which exceeds the time limit under the given constraints (\(N, Q \le 2 \times 10^5\)) and results in TLE.

Therefore, we need a data structure that can answer each query in \(O(\log N)\) or \(O(\log^2 N)\) time.

2. How to Merge Intervals (Considering a Segment Tree)

To efficiently process interval queries, we consider using a Segment Tree. Each node of the segment tree stores the following information: - max_val: The maximum elevation of mountains in that interval - cnt: The number of visible mountains when viewing that interval alone from the left

The key challenge is how to merge two intervals (left child \(L\) and right child \(R\)) to compute the parent node \(u\)’s information (push_up).

• Updating the maximum value: The maximum value of \(u\) is simply the larger of the two children’s maximum values. $\(\text{tree}[u].\text{max\_val} = \max(\text{tree}[L].\text{max\_val}, \text{tree}[R].\text{max\_val})\)$

• Updating the visible mountain count: All mountains visible in the left child’s interval \(L\) are also visible in the parent’s interval. On the other hand, the mountains visible in the right child’s interval \(R\) are restricted to those with height at least \(\text{tree}[L].\text{max\_val}\) (the maximum value of the left child’s interval).

Therefore, we need a function (called right_query here) that efficiently computes “how many mountains with height at least \(x\) are visible when looking from the left” within the right child’s interval.

---

Algorithm

1. Design of right_query(u, l, r, x)

For node \(u\) (representing interval \([l, r]\)), this function returns the number of visible mountains when looking from the left, under the assumption that “the current maximum value so far is \(x\).”

Using the structure of the segment tree, this can be computed recursively as follows: - Base case (when \(l = r\)): This is a leaf node, so return \(1\) if the mountain’s height is at least \(x\), and \(0\) otherwise. - Recursive step: Let \(L\) be the left child and \(R\) be the right child of node \(u\). 1. If the left child’s maximum \(\text{tree}[L].\text{max\_val} < x\): All mountains in the left child are below \(x\), so none are visible from the left child. Therefore, we only need to search the right child: call right_query(R, mid + 1, r, x). 2. If the left child’s maximum \(\text{tree}[L].\text{max\_val} \ge x\): There exists at least one mountain with height \(\ge x\) somewhere in the left child. In this case, the number of visible mountains from the right child equals the number of mountains visible using the left child’s maximum \(\text{tree}[L].\text{max\_val}\) as the threshold. This can be computed in constant time \(O(1)\) as \(\text{tree}[u].\text{cnt} - \text{tree}[L].\text{cnt}\) (i.e., the total visible count of node \(u\) minus the visible count of the left child alone). Thus, we return the result of right_query(L, l, mid, x) plus this contribution from the right child.

Since right_query only recurses into one of the two children at each step, it runs in \(O(\log N)\) time, proportional to the height of the tree.

2. Building and Updating the Segment Tree

The push_up procedure for merging the left and right children is performed as follows:

void push_up(int u, int l, int r) {
    int mid = (l + r) / 2;
    int L = 2 * u;
    int R = 2 * u + 1;
    tree[u].max_val = max(tree[L].max_val, tree[R].max_val);
    // Compute how many mountains in the right child's interval are visible
    // given that the left child's maximum serves as the threshold
    tree[u].cnt = tree[L].cnt + right_query(R, mid + 1, r, tree[L].max_val);
}

Since push_up calls right_query once, the merge operation takes \(O(\log N)\) time. The total time complexity for building the segment tree is \(O(N \log N)\).

3. Query Processing

We process queries for the interval \([L_j, R_j]\). The general approach is similar to a standard segment tree range query, but we need to maintain the “maximum value seen so far from the left” as we proceed.

We prepare global variables (or references): cur_max (the maximum elevation encountered so far, initially \(0\)) and ans_cnt (the total count of visible mountains, initially \(0\)). We traverse the segment tree nodes covering the interval \([L_j, R_j]\) from left to right.

When we reach a node \(u\) (representing interval \([l, r]\)) that is completely contained within the query interval: 1. We compute the number of mountains visible with height at least cur_max in that node’s interval using right_query(u, l, r, cur_max), and add it to ans_cnt. 2. We update cur_max to \(\max(\text{cur\_max}, \text{tree}[u].\text{max\_val})\).

---

Complexity

Time Complexity

• Segment tree construction: \(O(N \log N)\) Each node’s merge (push_up) takes \(O(\log N)\), and there are \(O(N)\) nodes.
• Query processing: \(O(Q \log^2 N)\) For each query, the interval is split into \(O(\log N)\) nodes. For each node, a right_query taking \(O(\log N)\) is executed, so each query takes \(O(\log^2 N)\).
• Overall time complexity: \(O((N + Q) \log^2 N)\) Under the constraints \(N, Q \le 2 \times 10^5\), we have \(\log_2 N \approx 18\), so \((N + Q) \log^2 N \approx 1.3 \times 10^8\) basic operations, which comfortably fits within the time limit.

Space Complexity

• Space complexity: \(O(N)\) We maintain an array of size \(N\) and a segment tree with the number of leaves being the smallest power of two at least \(N\) (\(SZ \le 262,144\)), with total size \(2 \times SZ\). Thus, the space complexity is \(O(N)\).

---

Implementation Notes

1. Maintaining left-to-right order: In the query function, it is crucial to recursively process the left child before the right child. This ensures that cur_max always correctly represents “the maximum value of all elements to the left of the current position.”

   if (ql <= mid) {
      query(2 * u, l, mid, ql, qr); // Process left child first
   }
   if (qr > mid) {
      query(2 * u + 1, mid + 1, r, ql, qr); // Process right child after
   }
   

2. Sentinel values for non-leaf nodes: When \(N\) is not a power of two, the unused leaf nodes at the end of the segment tree should be initialized with a very small elevation value (such as -1) and a count of 0. This prevents out-of-bounds data from adversely affecting the computation.

   Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
int H[MAXN];

struct Node {
    int max_val;
    int cnt;
} tree[1 << 19];

int N, Q;
int SZ;

int right_query(int u, int l, int r, int x) {
    if (l > N) return 0;
    if (l == r) {
        return (tree[u].max_val >= x ? 1 : 0);
    }
    int mid = (l + r) / 2;
    int L = 2 * u;
    int R = 2 * u + 1;
    if (tree[L].max_val < x) {
        return right_query(R, mid + 1, r, x);
    } else {
        return right_query(L, l, mid, x) + (tree[u].cnt - tree[L].cnt);
    }
}

void push_up(int u, int l, int r) {
    int mid = (l + r) / 2;
    int L = 2 * u;
    int R = 2 * u + 1;
    tree[u].max_val = max(tree[L].max_val, tree[R].max_val);
    tree[u].cnt = tree[L].cnt + right_query(R, mid + 1, r, tree[L].max_val);
}

void build(int u, int l, int r) {
    if (l == r) {
        if (l <= N) {
            tree[u].max_val = H[l];
            tree[u].cnt = 1;
        } else {
            tree[u].max_val = -1;
            tree[u].cnt = 0;
        }
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    push_up(u, l, r);
}

int ans_cnt;
int cur_max;

void query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        ans_cnt += right_query(u, l, r, cur_max);
        cur_max = max(cur_max, tree[u].max_val);
        return;
    }
    int mid = (l + r) / 2;
    if (ql <= mid) {
        query(2 * u, l, mid, ql, qr);
    }
    if (qr > mid) {
        query(2 * u + 1, mid + 1, r, ql, qr);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N >> Q)) return 0;

    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }

    SZ = 1;
    while (SZ < N) SZ *= 2;

    build(1, 1, SZ);

    for (int j = 0; j < Q; ++j) {
        int L, R;
        cin >> L >> R;
        ans_cnt = 0;
        cur_max = 0;
        query(1, 1, SZ, L, R);
        cout << ans_cnt << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.