概要

各クエリ \([L, R]\) について、その中に完全に含まれる「安定配置」な連続部分区間の個数を求めます。

重要なのは、ある位置 \(i\) から始まる安定配置の右端は「\(A_i\) より小さい値が初めて現れる直前まで」と分かることです。

考察

区間 \([l, r]\) が安定配置である条件を考えます。

条件は、各 \(j\) に対して、左側に \(A_i \leq A_j\) となる荷物 \(i\) が存在することです。

特に \(j = l+1\) のとき、左側には \(l\) しかないので、必ず \(A_l \leq A_{l+1}\) が必要です。

さらに、もし区間内で初めて \(A_l\) より小さい値が現れた位置を \(p\) とすると、\(p\) より左の値はすべて \(A_p\) より大きいので、\(p\) を支える荷物が存在せず、条件を満たせません。

したがって、区間 \([l, r]\) が安定配置であることは、次と同値です。

• \(A_l \leq A_j\) がすべての \(j \in [l, r]\) で成り立つ
• つまり、左端 \(A_l\) が区間内の最小値の \(1\) つである

そこで、各位置 \(i\) について次を定義します。

\(B_i =\) 位置 \(i\) より右で初めて \(A_i\) より小さい値が現れる位置

そのような位置がなければ \(B_i = N+1\) とします。

すると、位置 \(i\) から始まる安定配置な区間の右端は、

• \(i, i+1, \dots, B_i - 1\)

まで選べます。

クエリ \([L, R]\) に対して、開始位置を \(i\) とすると、右端は \(R\) を超えられないので、選べる右端の個数は

\(min(B_i, R+1) - i\)

です。

よって答えは

\(sum_{i=L}^{R} \left( min(B_i, R+1) - i \right)\)

になります。

素朴に各クエリで \(i=L\) から \(R\) まで足し合わせると、最悪で \(O(NQ)\) となり、制約上間に合いません。

そこで、\(min(B_i, R+1)\) の和を高速に求めるために、クエリを \(R+1\) の小さい順に処理します。

アルゴリズム

まず、各 \(i\) に対する \(B_i\) を求めます。

これは「右側で最初に現れる、自分より小さい値」なので、単調スタックで \(O(N)\) で求められます。

右から左へ見ていき、スタックには候補となる位置を保持します。

• \(A_{st.top()} \geq A_i\) なら、その位置は \(A_i\) より小さくないので削除
• 残った先頭が、\(i\) より右で最初に現れる \(A_i\) より小さい位置
• なければ \(B_i = N+1\)

ここで、等しい値は条件を壊さないので、「より小さい」を探す必要があります。そのため、\(A_{st.top()} \geq A_i\) の間 pop します。

次に、クエリをオフラインで処理します。

クエリ \([L, R]\) に対して \(x = R+1\) とおきます。

求めたいのは

\(sum_{i=L}^{R} min(B_i, x) - sum_{i=L}^{R} i\)

です。

ここで、\(B_i \leq x\) の位置は \(min(B_i, x) = B_i\)、
\(B_i > x\) の位置は \(min(B_i, x) = x\) です。

そこで、\(x\) を \(1\) から \(N+1\) まで増やしながら、

• \(B_i = x\) になった位置 \(i\) を Fenwick Tree に追加する
• Fenwick Tree で、現在 \(B_i \leq x\) である位置の個数と、\(B_i\) の合計を管理する

という処理をします。

Fenwick Tree は \(2\) つ使います。

• bitCnt: \(B_i \leq x\) となった位置の個数
• bitSum: それらの \(B_i\) の合計

クエリ \([L, R]\) を \(x = R+1\) のタイミングで処理するとします。

\([L, R]\) 内で、すでに追加済みの位置数を cnt、その \(B_i\) の合計を sumB とすると、

• 追加済みの位置は \(min(B_i, x) = B_i\)
• 未追加の位置は \(min(B_i, x) = x\)

なので、

\(sumMin = sumB + x \times ((R-L+1) - cnt)\)

となります。

また、

\(sum_{i=L}^{R} i = \frac{(L+R)(R-L+1)}{2}\)

なので、答えは

\(sumMin - \frac{(L+R)(R-L+1)}{2}\)

です。

計算量

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

実装のポイント

• \(B_i\) は「次に現れる strictly smaller な位置」です。等しい値では安定配置は壊れないため、単調スタックでは A[st.back()] >= A[i] の間 pop します。

• 答えは最大で \(O(N^2)\) になるため、long long を使います。

• \(B_i\) が存在しない場合は番兵として \(N+1\) を入れます。

• クエリ \([L, R]\) は \(x = R+1\) のタイミングで処理します。これにより、\(min(B_i, R+1)\) の和を Fenwick Tree で効率よく求められます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}

    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum_prefix(int idx) const {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    long long sum_range(int l, int r) const {
        if (l > r) return 0;
        return sum_prefix(r) - sum_prefix(l - 1);
    }
};

struct Query {
    int l, r, id;
};

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

    int N, Q;
    cin >> N >> Q;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<int> nxt(N + 1, N + 1);
    vector<int> st;

    for (int i = N; i >= 1; i--) {
        while (!st.empty() && A[st.back()] >= A[i]) st.pop_back();
        if (!st.empty()) nxt[i] = st.back();
        st.push_back(i);
    }

    vector<vector<int>> bucket(N + 2);
    for (int i = 1; i <= N; i++) {
        bucket[nxt[i]].push_back(i);
    }

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

    Fenwick bitCnt(N), bitSum(N);
    vector<long long> ans(Q);

    for (int x = 1; x <= N + 1; x++) {
        for (int pos : bucket[x]) {
            bitCnt.add(pos, 1);
            bitSum.add(pos, x);
        }

        for (const auto& q : queries[x]) {
            long long len = q.r - q.l + 1LL;
            long long cnt = bitCnt.sum_range(q.l, q.r);
            long long sumB = bitSum.sum_range(q.l, q.r);

            long long sumMin = sumB + 1LL * x * (len - cnt);
            long long sumIdx = 1LL * (q.l + q.r) * len / 2;

            ans[q.id] = sumMin - sumIdx;
        }
    }

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

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。