概要

この問題は、与えられた配列の区間クエリに対して、条件を満たす連続部分区間（安定配置）の個数を高速に求める問題です。 条件を数式で整理し、平面走査（クエリの先読み）、セグメント木、そして Fenwick Tree (BIT) を組み合わせることで、各クエリに対して高速に応答します。

---

考察

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

区間 \([l, r]\) が安定配置であるとは、すべての \(j \in [l+1, r]\) について、以下を満たす \(i\) が存在することです： - \(l \leq i < j\) かつ \(A_i \leq A_j\)

ここで、各 \(j\) に対し、「自分より左側にあり、自分以下の重さを持つ最大のインデックス」 を \(P_j\) と定義します。すなわち、 $\(P_j = \max \{ i < j \mid A_i \leq A_j \}\)\( （そのような \)i\( が存在しない場合は \)P_j = 0$ とします）

この \(P_j\) を用いると、条件を満たす \(i\) が \(l\) 以上に存在するということは、「\(P_j \geq l\) である」 ことと同値になります。 したがって、区間 \([l, r]\) が安定配置であるための条件は、以下のようにシンプルに言い換えられます。

\[\text{すべての } j \in [l+1, r] \text{ について、} P_j \geq l\]

2. 左端 \(l\) を固定したときに右端 \(r\) がどこまで伸ばせるか

左端 \(l\) を固定したとき、\([l, r]\) が安定配置となる最大の右端を \(R_{\max}[l]\) とします。 もしある \(j > l\) で \(P_j < l\) となってしまうと、右端を \(j\) 以上にすることはできません。したがって、\(R_{\max}[l]\) は以下のように表せます。

\[R_{\max}[l] = \min \{ j - 1 \mid j > l \text{ かつ } P_j < l \}\]

（そのような \(j\) が存在しない場合は \(R_{\max}[l] = N\) とします）

このとき、左端が \(l\) であるような安定配置 \([l, r]\) の個数は、右端 \(r\) が \(l \leq r \leq R_{\max}[l]\) を満たすものであるため、全部で \(R_{\max}[l] - l + 1\) 個となります。

3. クエリ \([L, R]\) への適用

クエリ \([L, R]\) に完全に含まれる安定配置 \([l, r]\) （\(L \leq l \leq r \leq R\)）の個数を求めます。 左端 \(l\) を固定したとき、右端 \(r\) は \(R\) を超えることはできないため、動かせる範囲は \(l \leq r \leq \min(R, R_{\max}[l])\) となります。 よって、クエリに対する答えは以下の総和になります。

\[\sum_{l=L}^R \left( \min(R, R_{\max}[l]) - l + 1 \right)\]

この式は以下のように 3 つの部分に分解できます。

\[\sum_{l=L}^R \min(R, R_{\max}[l]) - \sum_{l=L}^R l + (R - L + 1)\]

• 第 2 項の \(\sum_{l=L}^R l\) は、等差数列の和の公式 \(\frac{(L + R)(R - L + 1)}{2}\) を用いて \(O(1)\) で計算できます。
• 第 3 項の \(R - L + 1\) も \(O(1)\) です。
• したがって、課題は 第 1 項の \(\sum_{l=L}^R \min(R, R_{\max}[l])\) を高速に求めること に帰着されます。

---

アルゴリズム

この問題を解くために、以下の 3 つのステップで処理を行います。

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

各 \(j\) について \(P_j = \max \{ i < j \mid A_i \leq A_j \}\) を求めます。 これは、配列を左から走査しながら、値とそのインデックスを保持する Max-BIT（最大値を取得できる Fenwick Tree） を用いることで、座標圧縮と合わせて \(O(N \log N)\) で計算できます。

ステップ 2: \(R_{\max}[l]\) の計算

\(R_{\max}[l]\) の定義は、「\(P_j < l < j\) となるような最小の \(j\) に対する \(j-1\)」でした。 これは、各 \(j\) について、区間 \([P_j + 1, j - 1]\) に対して \(j - 1\) で chmin（最小値更新）を適用する ことと同値です。 初期値をすべて \(N\) とした配列に対し、遅延評価セグメント木（Lazy Segment Tree）を用いて区間 chmin を行うことで、すべての \(R_{\max}[l]\) を \(O(N \log N)\) で求めることができます。

ステップ 3: クエリのオフライン処理（平面走査法）

\(\sum_{l=L}^R \min(R, R_{\max}[l])\) を求めるため、クエリを右端 \(R\) の昇順にソートして処理します。 \(R\) を \(1\) から \(N\) まで順に進めながら、各 \(l\) における \(\min(R, R_{\max}[l])\) の値を管理します。

各 \(l\) について、\(\min(R, R_{\max}[l])\) の挙動は以下の 2 つの状態に分かれます。 1. 変数状態: \(R_{\max}[l] \geq R\) のとき、値は \(R\) となり、 \(R\) の増加に伴って変化します。 2. 定数状態: \(R_{\max}[l] < R\) のとき、値は \(R_{\max}[l]\) で固定されます。

\(R\) を \(1\) 増やすとき、新しく \(R_{\max}[l] = R - 1\) となった \(l\) について、状態が「変数」から「定数（値は \(R-1\)）」へと変化します。 この状態変化を管理するために、2 つの Fenwick Tree を用意します。

• bit_var : \(l\) が変数状態なら \(1\)、定数状態なら \(0\) を保持する。
• bit_const : \(l\) が定数状態なら \(R_{\max}[l]\)、変数状態なら \(0\) を保持する。

【クエリ処理の流れ】 1. \(R\) を \(1\) から \(N\) までループする。 2. \(R_{\max}[l] = R - 1\) となる \(l\) について、状態を更新する： - bit_var の \(l\) 番目の値を \(-1\) する（\(1 \to 0\)）。 - bit_const の \(l\) 番目の値に \(R - 1\) を加える（\(0 \to R - 1\)）。 3. 右端が \(R\) であるようなクエリ \([L, R]\) に対して、以下のように和を計算する： - \(\sum_{l=L}^R \min(R, R_{\max}[l]) = (\text{bit\_const の } [L, R] \text{ の和}) + (\text{bit\_var の } [L, R] \text{ の和}) \times R\) 4. 得られた値から等差数列の和などを引き、クエリの答えを記録する。

---

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 座標圧縮と \(P_j\) の計算に \(O(N \log N)\)
  • 遅延セグメント木による \(R_{\max}[l]\) の計算に \(O(N \log N)\)
  • クエリのソートと Fenwick Tree を用いた平面走査に \(O((N + Q) \log N)\)
• 空間計算量: \(O(N + Q)\)
  • 各種配列、セグメント木、Fenwick Tree、およびクエリの保存に必要なメモリはすべて \(O(N + Q)\) です。

---

実装のポイント

1. 座標圧縮: 重さ \(A_i\) の値は最大で \(10^9\) と大きいため、そのままでは BIT のインデックスとして使えません。あらかじめ重複を排除してソートした配列 U を用意し、二分探索（lower_bound）を用いて \(1\) から始まるコンパクトな整数に変換（座標圧縮）しています。

2. 遅延セグメント木のモノイド設計: \(R_{\max}[l]\) を求めるための区間 chmin 操作には、Atcoder Library (ACL) の lazy_segtree を使用しています。

   • op は区間の最小値を取得する min(a, b)

   • mapping は lazy に伝播された値で chmin を行う min(f, x) として定義し、適切に区間更新を行っています。

     ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/lazysegtree>
#include <atcoder/fenwicktree>

using namespace std;
using namespace atcoder;

// MaxBIT for calculating P_j
struct MaxBIT {
    int n;
    vector<int> tree;
    MaxBIT(int n) : n(n), tree(n + 1, 0) {}
    void update(int i, int val) {
        for (; i <= n; i += i & -i) {
            tree[i] = max(tree[i], val);
        }
    }
    int query(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res = max(res, tree[i]);
        }
        return res;
    }
};

// lazy_segtree settings for range chmin
using S = int;
using F = int;
S op(S a, S b) { return min(a, b); }
S e() { return 1e9; }
S mapping(F f, S x) { return min(f, x); }
F composition(F f, F g) { return min(f, g); }
F id() { return 1e9; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Coordinate compression for A
    vector<int> U = A;
    sort(U.begin(), U.end());
    U.erase(unique(U.begin(), U.end()), U.end());
    auto get_idx = [&](int x) {
        return lower_bound(U.begin(), U.end(), x) - U.begin();
    };

    // Calculate P_j (1-based index)
    MaxBIT bit_pos(U.size());
    vector<int> P(N + 1, 0);
    for (int j = 1; j <= N; ++j) {
        int x = get_idx(A[j - 1]) + 1;
        P[j] = bit_pos.query(x);
        bit_pos.update(x, j);
    }

    // Calculate R_max[l] using range chmin
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(N + 2);
    for (int i = 0; i <= N + 1; ++i) {
        seg.set(i, N);
    }
    for (int j = 1; j <= N; ++j) {
        int l = P[j] + 1;
        int r = j;
        if (l < r) {
            seg.apply(l, r, j - 1);
        }
    }

    vector<int> R_max(N + 1);
    for (int l = 1; l <= N; ++l) {
        R_max[l] = seg.get(l);
    }

    // Offline query processing
    vector<vector<int>> ev(N + 1);
    for (int l = 1; l <= N; ++l) {
        ev[R_max[l]].push_back(l);
    }

    vector<vector<pair<int, int>>> queries(N + 1);
    for (int q = 0; q < Q; ++q) {
        int L, R;
        cin >> L >> R;
        queries[R].push_back({L, q});
    }

    fenwick_tree<long long> bit_const(N + 1);
    fenwick_tree<long long> bit_var(N + 1);
    for (int l = 1; l <= N; ++l) {
        bit_var.add(l, 1);
    }

    vector<long long> ans(Q);
    for (int R = 1; R <= N; ++R) {
        for (int l : ev[R - 1]) {
            bit_var.add(l, -1);
            bit_const.add(l, R - 1);
        }
        for (auto [L, id] : queries[R]) {
            long long sum_min = bit_const.sum(L, R + 1) + bit_var.sum(L, R + 1) * R;
            long long sum_l = (long long)(L + R) * (R - L + 1) / 2;
            ans[id] = sum_min - sum_l + (R - L + 1);
        }
    }

    for (int q = 0; q < Q; ++q) {
        cout << ans[q] << "\n";
    }

    return 0;
}

---

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