概要

この問題は、与えられた山脈の特定の区間 \([L_j, R_j]\) を左（西）から眺めたときに「見える」山の個数を、各クエリに対して高速に求める問題です。

ある山が見えるとは、「その山より左側（区間内）に、自分より厳密に高い山が存在しない」ことを意味します。これは、左から順に見ていったときの「これまでの最大標高」を更新（または維持）する山をカウントすることに相当します。

---

考察

1. 愚直なアプローチとその限界

各クエリ \([L_j, R_j]\) に対して、左端 \(L_j\) から右端 \(R_j\) まで実際に走査し、それまでの最大標高を更新しながら見える山を数え上げる方法が考えられます。 しかし、この方法では1回のクエリに最悪 \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、制約（\(N, Q \le 2 \times 10^5\)）のもとでは実行時間制限に間に合いません（TLE）。

したがって、各クエリに対して \(O(\log N)\) や \(O(\log^2 N)\) などの高速な時間で答えを求めるデータ構造が必要になります。

2. 区間のマージをどう行うか（セグメント木の検討）

区間に対するクエリを高速に処理するため、セグメント木（Segment Tree）の利用を考えます。 セグメント木の各ノードに、以下の情報を持たせることにします。 - max_val: その区間における山の最大標高 - cnt: その区間単体を左から見たときに、見える山の個数

ここで問題となるのは、2つの区間（左の子 \(L\) と右の子 \(R\)）をマージして親のノード \(u\) の情報を計算する（push_up）方法です。

• 最大値の更新: \(u\) の最大値は、単純に左右の子の最大値の大きい方です。 $\(\text{tree}[u].\text{max\_val} = \max(\text{tree}[L].\text{max\_val}, \text{tree}[R].\text{max\_val})\)$

• 見える山の個数の更新: 左の子の区間 \(L\) で見える山は、親の区間でもすべて見えます。 一方、右の子の区間 \(R\) で見える山は、「左の子の区間の最大値 \(\text{tree}[L].\text{max\_val}\) 以上の高さを持つもの」に制限されます。

したがって、右の子の区間において「高さ \(x\) 以上の山が、左から見ていくつ見えるか」を高速に求める関数（ここでは right_query と呼びます）が必要になります。

---

アルゴリズム

1. right_query(u, l, r, x) の設計

ノード \(u\)（区間 \([l, r]\) を表す）において、左から見たときに「これまでの最大値が \(x\) である」という前提のもとで、見える山の個数を返します。

セグメント木の構造を利用して、以下のように再帰的に求められます。 - ベースケース (\(l = r\) のとき): 葉ノードなので、その山の高さが \(x\) 以上なら \(1\)、未満なら \(0\) を返します。 - 再帰ステップ: ノード \(u\) の左の子を \(L\)、右の子を \(R\) とします。 1. 左の子の最大値 \(\text{tree}[L].\text{max\_val} < x\) の場合: 左の子の山はすべて \(x\) 未満なので、左の子からは1つも見えません。 したがって、右の子だけを探索すればよいため、right_query(R, mid + 1, r, x) を呼び出します。 2. 左の子の最大値 \(\text{tree}[L].\text{max\_val} \ge x\) の場合: 左の子のどこかに \(x\) 以上の山が存在します。 このとき、右の子から見える山の数は、左の子の最大値 \(\text{tree}[L].\text{max\_val}\) を基準として見える山の数と等しくなります。 これは、親ノード \(u\) の全体で見える山の数 \(\text{tree}[u].\text{cnt}\) から、左の子だけで見える山の数 \(\text{tree}[L].\text{cnt}\) を引いた値（すなわち \(\text{tree}[u].\text{cnt} - \text{tree}[L].\text{cnt}\)）として定数時間 \(O(1)\) で求められます。 よって、左の子に対する探索結果 right_query(L, l, mid, x) に、この右の子の寄与分を足した値を返します。

この right_query は、再帰の各ステップで左右どちらか片方の子ノードにしか進まないため、木の高さに比例する \(O(\log N)\) の時間で計算できます。

2. セグメント木の構築と更新

左右の子をマージする push_up 処理は以下のように行います。

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);
}

push_up の中で right_query を1回呼び出すため、マージにかかる時間は \(O(\log N)\) です。 セグメント木の構築全体の計算量は \(O(N \log N)\) となります。

3. クエリ処理

クエリ区間 \([L_j, R_j]\) に対する処理を行います。 大まかな流れは通常のセグメント木の区間クエリと同様ですが、「左から順に走査したときの最大値」を保持しながら進める必要があります。

グローバル変数（または参照）として cur_max（これまでに遭遇した最大標高、初期値 \(0\)）と ans_cnt（見える山の総数、初期値 \(0\)）を用意します。 区間 \([L_j, R_j]\) をカバーするセグメント木のノードを左から順に探索します。

完全にクエリ区間に含まれるノード \(u\)（区間 \([l, r]\)）に到達したとき： 1. そのノードの区間のうち、現在の最大値 cur_max 以上の高さで見える山の数を right_query(u, l, r, cur_max) によって求め、ans_cnt に加算します。 2. cur_max を \(\max(\text{cur\_max}, \text{tree}[u].\text{max\_val})\) に更新します。

---

計算量

時間計算量

• セグメント木の構築: \(O(N \log N)\) 各ノードのマージ（push_up）に \(O(\log N)\) かかり、ノード数は \(O(N)\) 個であるため。
• クエリ処理: \(O(Q \log^2 N)\) 1つのクエリにおいて、区間は \(O(\log N)\) 個のノードに分割されます。それぞれのノードに対して \(O(\log N)\) の right_query を実行するため、1クエリあたり \(O(\log^2 N)\) となります。
• 全体時間計算量: \(O((N + Q) \log^2 N)\) 制約 \(N, Q \le 2 \times 10^5\) において、\(\log_2 N \approx 18\) であるため、\((N + Q) \log^2 N \approx 1.3 \times 10^8\) 回程度の基本演算となり、実行時間制限に十分間に合います。

空間計算量

• 空間計算量: \(O(N)\) サイズ \(N\) の配列と、葉の数が \(N\) 以上の最小の2のべき乗（\(SZ \le 262,144\)）となるセグメント木（サイズ \(2 \times SZ\)）を保持するため、空間計算量は \(O(N)\) です。

---

実装のポイント

1. 左からの順序の維持: クエリ処理の関数 query 内で、左の子を右の子よりも先に再帰呼び出しすることが非常に重要です。これにより、cur_max が常に「現在より左側にあるすべての要素の最大値」を正しく表すようになります。

   if (ql <= mid) {
      query(2 * u, l, mid, ql, qr); // 左の子を先に処理
   }
   if (qr > mid) {
      query(2 * u + 1, mid + 1, r, ql, qr); // 右の子を後に処理
   }
   

2. 葉ノード以外の番兵: \(N\) が2のべき乗でない場合、セグメント木の末尾の余った葉ノードには、標高として極小値（-1など）、カウントとして 0 を入れて初期化することで、境界外のデータが計算に悪影響を及ぼさないようにします。

   ソースコード

#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;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。