概要

各クエリ \([L, R]\) について、その中に完全に含まれる連続部分区間 \([l, r]\) のうち、「左端の荷物が区間内で最小値になっている」ものの個数を数えます。

考察

安定配置の条件を言い換えます。

区間 \([l, r]\) が安定配置であるとは、各 \(j\) \((l < j \leq r)\) について、左側に \(A_i \leq A_j\) となる荷物 \(i\) が存在することです。

ここで重要な観察は、区間 \([l, r]\) が安定配置であるための必要十分条件は、

\[ A_l \leq A_j \quad (l \leq j \leq r) \]

つまり、左端 \(l\) の荷物が区間内の最小値であることです。

なぜなら、もしすべての \(j\) について \(A_l \leq A_j\) なら、各荷物 \(j\) は左端の荷物 \(l\) を支えにできます。

逆に、途中で初めて \(A_l\) より小さい荷物が現れたとします。その荷物は、それより左に自分以下の重さの荷物が存在しないため、条件を満たせません。

したがって、問題は次のように言い換えられます。

各クエリ \([L, R]\) について、\(L \leq l \leq r \leq R\) かつ、\(A_l\) が \([l, r]\) 内の最小値であるような区間 \([l, r]\) の個数を求める。

---

各位置 \(i\) について、右側で初めて \(A_i\) より小さい値が現れる位置を考えます。

これを

\[ \mathrm{nxt}[i] \]

とします。

つまり、

\[ \mathrm{nxt}[i] = \min \{ j > i \mid A_j < A_i \} \]

です。

そのような \(j\) が存在しない場合は、

\[ \mathrm{nxt}[i] = N + 1 \]

とします。

すると、左端を \(i\) に固定したとき、安定配置になる区間の右端 \(r\) は

\[ i \leq r < \mathrm{nxt}[i] \]

を満たす必要があります。

なぜなら、\(\mathrm{nxt}[i]\) より前には \(A_i\) より小さい値が存在しないからです。

したがって、クエリ \([L, R]\) に対する答えは、

\[ \sum_{i=L}^{R} \left( \min(\mathrm{nxt}[i], R+1) - i \right) \]

になります。

例えば、右端の上限が \(R\) なので、実際に選べる右端は

\[ i, i+1, \dots, \min(\mathrm{nxt}[i]-1, R) \]

です。

その個数は

\[ \min(\mathrm{nxt}[i], R+1) - i \]

です。

---

素朴に各クエリごとにすべての部分区間を調べると、最悪で \(O(N^2Q)\) となり間に合いません。

また、各クエリで \(i=L\) から \(R\) まで走査して上の式を計算しても、最悪で \(O(NQ)\) となり、\(N,Q \leq 2 \times 10^5, 10^5\) では間に合いません。

そこで、クエリをオフラインで処理し、Fenwick Tree を使って高速に総和を求めます。

アルゴリズム

まず、各 \(i\) について \(\mathrm{nxt}[i]\) を求めます。

これは単調スタックを使うと \(O(N)\) で求められます。

右から左へ見ていき、現在の値以上のものをスタックから取り除きます。

すると、スタックの先頭には「右側で最も近い、自分より小さい値の位置」が残ります。

---

次に、各クエリ \([L, R]\) に対して

\[ \sum_{i=L}^{R} \left( \min(\mathrm{nxt}[i], R+1) - i \right) \]

を計算します。

ここで、

\[ x = R + 1 \]

とおきます。

すると必要なのは、

\[ \sum_{i=L}^{R} \min(\mathrm{nxt}[i], x) - \sum_{i=L}^{R} i \]

です。

\(\sum_{i=L}^{R} i\) は等差数列の和で簡単に求められます。

問題は

\[ \sum_{i=L}^{R} \min(\mathrm{nxt}[i], x) \]

です。

これは、\(\mathrm{nxt}[i] \leq x\) のものと、\(\mathrm{nxt}[i] > x\) のものに分けます。

• \(\mathrm{nxt}[i] \leq x\) の場合、\(\min(\mathrm{nxt}[i], x) = \mathrm{nxt}[i]\)
• \(\mathrm{nxt}[i] > x\) の場合、\(\min(\mathrm{nxt}[i], x) = x\)

したがって、

\[ \sum_{i=L}^{R} \min(\mathrm{nxt}[i], x) = \sum_{\substack{i=L \\ \mathrm{nxt}[i] \leq x}}^{R} \mathrm{nxt}[i] + x \times \#\{i \in [L,R] \mid \mathrm{nxt}[i] > x\} \]

となります。

これを高速に求めるために、クエリを \(x=R+1\) の昇順に並べます。

また、各位置 \(i\) を \(\mathrm{nxt}[i]\) の昇順に並べます。

クエリを順番に処理しながら、\(\mathrm{nxt}[i] \leq x\) になった位置 \(i\) を Fenwick Tree に追加します。

Fenwick Tree は 2 本使います。

• bit_cnt: 追加済みの位置の個数
• bit_sum: 追加済みの位置の \(\mathrm{nxt}[i]\) の総和

クエリ \([L, R]\) に対して、

• cnt: \([L,R]\) 内で \(\mathrm{nxt}[i] \leq x\) の個数
• sumb: \([L,R]\) 内で \(\mathrm{nxt}[i] \leq x\) の \(\mathrm{nxt}[i]\) の総和

を Fenwick Tree から求めます。

区間の長さを

\[ \mathrm{len} = R - L + 1 \]

とすると、\(\mathrm{nxt}[i] > x\) の個数は

\[ \mathrm{len} - \mathrm{cnt} \]

です。

よって、

\[ \sum_{i=L}^{R} \min(\mathrm{nxt}[i], x) = \mathrm{sumb} + x(\mathrm{len} - \mathrm{cnt}) \]

です。

最後に、

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

を引けば答えになります。

つまり答えは、

\[ \mathrm{sumb} + x(\mathrm{len} - \mathrm{cnt}) - \frac{(L+R)(R-L+1)}{2} \]

です。

計算量

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

\(\mathrm{nxt}\) の計算は単調スタックにより \(O(N)\) です。

その後、各位置の追加と各クエリ処理で Fenwick Tree を使うため、全体で \(O((N+Q)\log N)\) になります。

実装のポイント

単調スタックでは、右から左に走査します。

while st and A[st[-1]] >= A[i]:
    st.pop()

として、自分以上の値を取り除きます。

これにより、スタックの末尾に残るのは「自分より小さい値」のうち最も近い位置になります。

また、Fenwick Tree では位置 \(i\) に対して、

• 個数として \(1\)
• 総和として \(\mathrm{nxt}[i]\)

を追加します。

クエリは元の順番で答える必要があるため、クエリ番号 idx を保持しておき、最後に ans[idx] に格納します。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    A = [0] + [next(it) for _ in range(N)]

    nxt = [N + 1] * (N + 1)
    st = []
    for i in range(N, 0, -1):
        ai = A[i]
        while st and A[st[-1]] >= ai:
            st.pop()
        if st:
            nxt[i] = st[-1]
        st.append(i)

    items = sorted((nxt[i], i) for i in range(1, N + 1))

    queries = []
    for idx in range(Q):
        L = next(it)
        R = next(it)
        queries.append((R + 1, L, R, idx))
    queries.sort()

    bit_cnt = [0] * (N + 2)
    bit_sum = [0] * (N + 2)

    def add(bit, idx, val):
        while idx <= N:
            bit[idx] += val
            idx += idx & -idx

    def sum_bit(bit, idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    ans = [0] * Q
    p = 0

    for x, L, R, qi in queries:
        while p < N and items[p][0] <= x:
            b, pos = items[p]
            add(bit_cnt, pos, 1)
            add(bit_sum, pos, b)
            p += 1

        cnt = sum_bit(bit_cnt, R) - sum_bit(bit_cnt, L - 1)
        sumb = sum_bit(bit_sum, R) - sum_bit(bit_sum, L - 1)

        length = R - L + 1
        sum_idx = (L + R) * length // 2
        ans[qi] = sumb + x * (length - cnt) - sum_idx

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

if __name__ == "__main__":
    main()

---

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