概要

この問題は、与えられた数列 \(A\) のクエリ区間 \([L_k, R_k]\) 内に完全に含まれる「安定配置」となる連続部分区間の個数を求める問題です。 各要素の関係性を整理し、条件を数式に落とし込むことで、平面走査（クエリの先読み）とフェニック木（BIT）を用いた高速なクエリ処理に帰着させます。

---

考察

1. 安定配置の条件の言い換え

区間 \([l, r]\) が安定配置であるとは、任意の \(j \in (l, r]\) について、「左側に自分以下の重さの荷物がある」ということです。 ここで、各 \(j\) について「自分より左にあり、かつ重さが自分以下であるような荷物のうち、最も右にあるもののインデックス」を \(P_j\) と定義します。 $\(P_j = \max \{ i < j \mid A_i \leq A_j \}\)\( （存在しない場合は \)P_j = 0$ とします）

このとき、区間 \([l, r]\) が安定配置であるための必要十分条件は、以下のように言い換えられます。

任意の \(j \in [l+1, r]\) について、 \(P_j \geq l\) である。

なぜなら、ある \(j\) について \(P_j < l\) であると、区間 \([l, j-1]\) の中には \(A_j\) 以下の重さの荷物が存在しないため、安定して積むことができなくなってしまうからです。

2. 左端 \(l\) に対する最大の右端 \(V_l\)

左端 \(l\) を固定したとき、右端 \(r\) をどこまで右に伸ばせるかを考えます。 上記条件より、 \(P_j < l\) となるような \(j\) が現れた時点で、それ以上右に伸ばすことはできません。 そこで、 \(P_j < l\) となる最小の \(j > l\) を \(nxt_l\) と定義します。 $\(nxt_l = \min \{ j > l \mid P_j < l \}\)\( （存在しない場合は \)nxt_l = N + 1$）

これより、左端 \(l\) に対応する最大の右端 \(V_l\) は \(V_l = nxt_l - 1\) となります。 このとき、左端が \(l\) であるような安定配置の右端 \(r\) は、 \(l \leq r \leq V_l\) を満たすすべての範囲が選べるため、その個数は \(V_l - l + 1\) 個となります。

3. クエリ \([L, R]\) に対する答えの数式化

クエリ区間 \([L, R]\) に完全に含まれる安定配置 \([l, r]\) の個数を求めます。これは \(L \leq l \leq r \leq R\) かつ \(r \leq V_l\) を満たす \((l, r)\) の組の個数です。

各 \(l \in [L, R]\) について、右端 \(r\) として選べるのは \(l \leq r \leq \min(R, V_l)\) の範囲です。 よって、その個数は \(\min(R, V_l) - l + 1\) 個となります。 これを \(l = L\) から \(R\) まで足し合わせたものがクエリの答えです。

\[\text{Ans} = \sum_{l=L}^{R} (\min(R, V_l) - l + 1) = \sum_{l=L}^{R} \min(R, V_l) - \sum_{l=L}^{R} l + (R - L + 1)\]

右側の \(\sum_{l=L}^{R} l\) は等差数列の和の公式を用いて \(O(1)\) で計算できます。 したがって、この問題は \(\sum_{l=L}^{R} \min(R, V_l)\) を高速に求める問題 に帰着されます。

---

アルゴリズム

本問題は以下の3つのステップで解くことができます。

ステップ1: \(P_j\) の計算

\(P_j = \max \{ i < j \mid A_i \leq A_j \}\) を求めます。 1. 数列 \(A\) を座標圧縮します。 2. 左から順に \(j = 1, \dots, N\) と走査します。 3. 重さの値をインデックスとし、その重さを持つ最新（最大）のインデックスを保持する BIT（最大値更新）を用意します。 4. \(A_j\) 以下の範囲での最大値を BIT から取得して \(P_j\) とし、その後 BIT の \(A_j\) の位置に \(j\) を登録します。

ステップ2: \(nxt_l\) の計算

\(nxt_l = \min \{ j > l \mid P_j < l \}\) を求めます。 1. \(l\) を \(N\) から \(1\) まで逆順に走査します。 2. \(P_j\) の値をインデックスとし、最小のインデックス \(j\) を保持する BIT（最小値更新）を用意します。 3. \(P_j \leq l-1\) となる最小の \(j\) を求めたいので、BIT から区間 \([0, l-1]\) の最小値を取得して \(nxt_l\) とします。 4. その後、BIT の \(P_l\) の位置に \(l\) を登録します。 5. \(V_l = nxt_l - 1\) を計算します。

ステップ3: 平面走査と BIT によるクエリ処理

\(\sum_{l=L}^{R} \min(R, V_l)\) を求めるため、クエリを右端 \(R\) でソートし、 \(R\) を \(1\) から \(N\) まで進めながら処理します（平面走査）。

\(V_l\) の値によって、 \(\min(R, V_l)\) は以下のように分岐します。 - \(V_l \leq R - 1\) のとき： \(\min(R, V_l) = V_l\) （値が確定） - \(V_l \geq R\) のとき： \(\min(R, V_l) = R\) （未確定）

\(R\) を進める際、 \(V_l = R - 1\) となる \(l\) を「確定済み」として、以下の2つの BIT に追加します。 - bit_cnt: 確定した \(l\) の位置に 1 を加算 - bit_sum: 確定した \(l\) の位置に V_l を加算

クエリ \([L, R]\) に対して、区間 \([L, R]\) 内での情報を BIT から取得します。 - 確定済みの個数: \(cnt = \text{query\_cnt}(R) - \text{query\_cnt}(L-1)\) - 確定済みの \(V_l\) の総和: \(sum = \text{query\_sum}(R) - \text{query\_sum}(L-1)\)

未確定の \(l\) の個数は \((R - L + 1) - cnt\) であり、これらに対する \(\min(R, V_l)\) の値はすべて \(R\) となります。 よって、求める総和は以下のように \(O(\log N)\) で計算できます。 $\(\sum_{l=L}^{R} \min(R, V_l) = sum + R \times (R - L + 1 - cnt)\)$

---

計算量

• 時間計算量: \(O((N + Q) \log N)\)

  • 座標圧縮に \(O(N \log N)\)
  • \(P_j\) および \(nxt_l\) の計算に、BIT の操作を含めて \(O(N \log N)\)
  • クエリのソートに \(O(Q \log Q)\)、平面走査と BIT によるクエリ処理に \(O((N + Q) \log N)\)
  • 全体として制限時間内に十分高速に動作します。

• 空間計算量: \(O(N + Q)\)

  • 数列、各種 BIT、クエリの保存に必要なメモリは \(N, Q\) に対して線形です。

---

実装のポイント

• 座標圧縮: 重さ \(A_i\) は最大 \(10^9\) と大きいため、BIT で管理できるように \(1\) から始まる順位（ランク）に座標圧縮を行います。

• 逆順の走査: \(nxt_l\) を求める際は、右側にある要素（\(j > l\)）の情報のみが必要なため、 \(l\) を右から左（\(N\) から \(1\)）へ走査しながら BIT を更新していく必要があります。

• 2つの BIT の役割: クエリ処理時に「個数」と「実際の値の総和」を別々に管理するために、bit_cnt と bit_sum の2つの BIT を並行して更新・利用します。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    Q = int(data[1])
    A = [int(x) for x in data[2 : N + 2]]

    # 座標圧縮
    vals = sorted(list(set(A)))
    val_to_rank = {v: i + 1 for i, v in enumerate(vals)}
    rank_A = [val_to_rank[x] for x in A]
    U = len(vals)

    # BIT for P_j (最大値)
    bit_P = [0] * (U + 1)

    P = [0] * (N + 1)
    for j in range(1, N + 1):
        r_A = rank_A[j - 1]
        # query_P(r_A)
        res = 0
        idx = r_A
        while idx > 0:
            if bit_P[idx] > res:
                res = bit_P[idx]
            idx -= idx & -idx
        P[j] = res

        # update_P(r_A, j)
        idx = r_A
        while idx <= U:
            if j > bit_P[idx]:
                bit_P[idx] = j
            idx += idx & -idx

    # BIT for nxt_l (最小値)
    INF = N + 1
    bit_nxt = [INF] * (N + 2)

    nxt = [0] * (N + 1)
    for l in range(N, 0, -1):
        # query_nxt(l - 1)
        idx = l  # (l - 1) + 1
        res = INF
        while idx > 0:
            if bit_nxt[idx] < res:
                res = bit_nxt[idx]
            idx -= idx & -idx
        nxt[l] = res

        # update_nxt(P[l], l)
        idx = P[l] + 1
        while idx <= N + 1:
            if l < bit_nxt[idx]:
                bit_nxt[idx] = l
            idx += idx & -idx

    # V_l = nxt[l] - 1
    V = [0] * (N + 1)
    pos = [[] for _ in range(N + 1)]
    for l in range(1, N + 1):
        V[l] = nxt[l] - 1
        pos[V[l]].append(l)

    queries = [[] for _ in range(N + 1)]
    idx_data = N + 2
    for q in range(Q):
        L = int(data[idx_data])
        R = int(data[idx_data + 1])
        idx_data += 2
        queries[R].append((L, q))

    ans = [0] * Q
    bit_cnt = [0] * (N + 1)
    bit_sum = [0] * (N + 1)

    for R in range(1, N + 1):
        for l in pos[R - 1]:
            # add_cnt(l, 1)
            idx = l
            while idx <= N:
                bit_cnt[idx] += 1
                idx += idx & -idx
            # add_sum(l, R - 1)
            idx = l
            while idx <= N:
                bit_sum[idx] += R - 1
                idx += idx & -idx

        for L, q_id in queries[R]:
            # query_cnt(R)
            res_cnt_R = 0
            idx = R
            while idx > 0:
                res_cnt_R += bit_cnt[idx]
                idx -= idx & -idx

            # query_cnt(L - 1)
            res_cnt_L = 0
            idx = L - 1
            while idx > 0:
                res_cnt_L += bit_cnt[idx]
                idx -= idx & -idx

            cnt = res_cnt_R - res_cnt_L

            # query_sum(R)
            res_sum_R = 0
            idx = R
            while idx > 0:
                res_sum_R += bit_sum[idx]
                idx -= idx & -idx

            # query_sum(L - 1)
            res_sum_L = 0
            idx = L - 1
            while idx > 0:
                res_sum_L += bit_sum[idx]
                idx -= idx & -idx

            s = res_sum_R - res_sum_L

            sum_min = s + R * (R - L + 1 - cnt)
            len_seg = R - L + 1
            sum_l = (L + R) * len_seg // 2
            ans[q_id] = sum_min - sum_l + len_seg

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    solve()

---

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