Overview

This problem asks us to find the number of contiguous subarrays that form a “stable arrangement” and are completely contained within the query interval \([L_k, R_k]\) of a given sequence \(A\). By organizing the relationships between elements and formulating the conditions mathematically, we reduce this to efficient query processing using sweep line (offline query processing) and Fenwick tree (BIT).

---

Analysis

1. Reformulating the Stable Arrangement Condition

An interval \([l, r]\) is a stable arrangement if, for every \(j \in (l, r]\), “there exists a package to its left with weight less than or equal to its own.” Here, for each \(j\), we define \(P_j\) as “the index of the rightmost element to the left of \(j\) whose weight is less than or equal to \(A_j\)”. $\(P_j = \max \{ i < j \mid A_i \leq A_j \}\)\( (If no such element exists, we set \)P_j = 0$)

Then, the necessary and sufficient condition for interval \([l, r]\) to be a stable arrangement can be restated as follows:

For all \(j \in [l+1, r]\), \(P_j \geq l\).

This is because if \(P_j < l\) for some \(j\), then there is no package with weight less than or equal to \(A_j\) within the interval \([l, j-1]\), making it impossible to stack stably.

2. Maximum Right Endpoint \(V_l\) for a Fixed Left Endpoint \(l\)

When fixing the left endpoint \(l\), we consider how far the right endpoint \(r\) can be extended. From the above condition, once a \(j\) with \(P_j < l\) appears, we cannot extend further to the right. So we define \(nxt_l\) as the smallest \(j > l\) such that \(P_j < l\). $\(nxt_l = \min \{ j > l \mid P_j < l \}\)\( (If no such element exists, \)nxt_l = N + 1$)

Thus, the maximum right endpoint corresponding to left endpoint \(l\) is \(V_l = nxt_l - 1\). In this case, the right endpoint \(r\) for stable arrangements with left endpoint \(l\) can be any value satisfying \(l \leq r \leq V_l\), giving a count of \(V_l - l + 1\).

3. Formulating the Answer for Query \([L, R]\)

We want to find the number of stable arrangements \([l, r]\) completely contained in the query interval \([L, R]\). This is the number of pairs \((l, r)\) satisfying \(L \leq l \leq r \leq R\) and \(r \leq V_l\).

For each \(l \in [L, R]\), the range of valid right endpoints \(r\) is \(l \leq r \leq \min(R, V_l)\). Thus, the count is \(\min(R, V_l) - l + 1\). The answer to the query is the sum of this over \(l = L\) to \(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)\]

The term \(\sum_{l=L}^{R} l\) on the right can be computed in \(O(1)\) using the arithmetic series formula. Therefore, this problem reduces to efficiently computing \(\sum_{l=L}^{R} \min(R, V_l)\).

---

Algorithm

This problem can be solved in the following three steps.

Step 1: Computing \(P_j\)

We compute \(P_j = \max \{ i < j \mid A_i \leq A_j \}\). 1. Coordinate-compress the sequence \(A\). 2. Scan from left to right for \(j = 1, \dots, N\). 3. Prepare a BIT (maximum value update) that uses weight values as indices and maintains the latest (largest) index holding each weight. 4. Query the BIT for the maximum value in the range up to \(A_j\) to obtain \(P_j\), then register \(j\) at position \(A_j\) in the BIT.

Step 2: Computing \(nxt_l\)

We compute \(nxt_l = \min \{ j > l \mid P_j < l \}\). 1. Scan \(l\) in reverse order from \(N\) down to \(1\). 2. Prepare a BIT (minimum value update) that uses \(P_j\) values as indices and maintains the minimum index \(j\). 3. Since we want the smallest \(j\) with \(P_j \leq l-1\), query the BIT for the minimum value in the range \([0, l-1]\) to obtain \(nxt_l\). 4. Then register \(l\) at position \(P_l\) in the BIT. 5. Compute \(V_l = nxt_l - 1\).

Step 3: Query Processing with Sweep Line and BIT

To compute \(\sum_{l=L}^{R} \min(R, V_l)\), we sort queries by their right endpoint \(R\) and process them while advancing \(R\) from \(1\) to \(N\) (sweep line).

Depending on the value of \(V_l\), \(\min(R, V_l)\) branches as follows: - When \(V_l \leq R - 1\): \(\min(R, V_l) = V_l\) (value is finalized) - When \(V_l \geq R\): \(\min(R, V_l) = R\) (not yet finalized)

As we advance \(R\), for each \(l\) with \(V_l = R - 1\), we mark it as “finalized” and add it to the following two BITs: - bit_cnt: Add 1 at position \(l\) for finalized entries - bit_sum: Add V_l at position \(l\) for finalized entries

For query \([L, R]\), we retrieve information for the interval \([L, R]\) from the BITs: - Number of finalized entries: \(cnt = \text{query\_cnt}(R) - \text{query\_cnt}(L-1)\) - Sum of finalized \(V_l\) values: \(sum = \text{query\_sum}(R) - \text{query\_sum}(L-1)\)

The number of unfinalized \(l\) values is \((R - L + 1) - cnt\), and for all of these, \(\min(R, V_l) = R\). Therefore, the desired sum can be computed in \(O(\log N)\) as follows: $\(\sum_{l=L}^{R} \min(R, V_l) = sum + R \times (R - L + 1 - cnt)\)$

---

Complexity

• Time Complexity: \(O((N + Q) \log N)\)

  • Coordinate compression: \(O(N \log N)\)
  • Computing \(P_j\) and \(nxt_l\) including BIT operations: \(O(N \log N)\)
  • Sorting queries: \(O(Q \log Q)\), sweep line and BIT query processing: \(O((N + Q) \log N)\)
  • Overall, this runs sufficiently fast within the time limit.

• Space Complexity: \(O(N + Q)\)

  • The memory required for the sequence, various BITs, and storing queries is linear in \(N\) and \(Q\).

---

Implementation Notes

• Coordinate Compression: Since weights \(A_i\) can be as large as \(10^9\), we perform coordinate compression to ranks starting from \(1\) so they can be managed by BITs.

• Reverse Scanning: When computing \(nxt_l\), since we only need information about elements to the right (\(j > l\)), we must scan \(l\) from right to left (\(N\) to \(1\)) while updating the BIT.

• Roles of the Two BITs: During query processing, we use two BITs, bit_cnt and bit_sum, updated and queried in parallel, to separately manage the “count” and the “sum of actual values.”

  Source Code

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()

---

This editorial was generated by gemini-3.5-flash-thinking.