Overview

This problem requires efficiently computing the number of contiguous subintervals (stable arrangements) satisfying a given condition for range queries on an array. By reformulating the condition mathematically and combining plane sweep (offline query processing), segment tree, and Fenwick Tree (BIT), we can answer each query efficiently.

---

Analysis

1. Reformulating the Stable Arrangement Condition

An interval \([l, r]\) is a stable arrangement if and only if for every \(j \in [l+1, r]\), there exists an \(i\) satisfying: - \(l \leq i < j\) and \(A_i \leq A_j\)

Here, for each \(j\), we define “the largest index to the left of \(j\) with weight at most \(A_j\)” as \(P_j\). That is, $\(P_j = \max \{ i < j \mid A_i \leq A_j \}\)\( (If no such \)i\( exists, we set \)P_j = 0$)

Using this \(P_j\), the existence of an \(i \geq l\) satisfying the condition is equivalent to “\(P_j \geq l\)”. Therefore, the condition for interval \([l, r]\) to be a stable arrangement can be simply restated as follows:

\[\text{For all } j \in [l+1, r], \text{ } P_j \geq l\]

2. How far the right endpoint \(r\) can extend when the left endpoint \(l\) is fixed

When the left endpoint \(l\) is fixed, let \(R_{\max}[l]\) be the maximum right endpoint such that \([l, r]\) is a stable arrangement. If there exists some \(j > l\) with \(P_j < l\), then the right endpoint cannot be \(j\) or larger. Therefore, \(R_{\max}[l]\) can be expressed as:

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

(If no such \(j\) exists, we set \(R_{\max}[l] = N\))

In this case, the number of stable arrangements \([l, r]\) with left endpoint \(l\) is the number of valid right endpoints \(r\) satisfying \(l \leq r \leq R_{\max}[l]\), which totals \(R_{\max}[l] - l + 1\).

3. Applying to Query \([L, R]\)

We want to count the number of stable arrangements \([l, r]\) (\(L \leq l \leq r \leq R\)) completely contained within query \([L, R]\). When the left endpoint \(l\) is fixed, the right endpoint \(r\) cannot exceed \(R\), so the valid range is \(l \leq r \leq \min(R, R_{\max}[l])\). Therefore, the answer to the query is the following sum:

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

This expression can be decomposed into 3 parts:

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

• The second term \(\sum_{l=L}^R l\) can be computed in \(O(1)\) using the arithmetic series formula \(\frac{(L + R)(R - L + 1)}{2}\).
• The third term \(R - L + 1\) is also \(O(1)\).
• Therefore, the problem reduces to efficiently computing the first term \(\sum_{l=L}^R \min(R, R_{\max}[l])\).

---

Algorithm

To solve this problem, we perform processing in the following 3 steps.

Step 1: Computing \(P_j\)

For each \(j\), we compute \(P_j = \max \{ i < j \mid A_i \leq A_j \}\). This can be computed in \(O(N \log N)\) by scanning the array from left to right and using a Max-BIT (Fenwick Tree that retrieves maximum values) combined with coordinate compression.

Step 2: Computing \(R_{\max}[l]\)

The definition of \(R_{\max}[l]\) is “the value \(j-1\) for the smallest \(j\) such that \(P_j < l < j\)”. This is equivalent to applying chmin (minimum update) with value \(j - 1\) to the interval \([P_j + 1, j - 1]\) for each \(j\). By performing range chmin operations on an array initialized entirely to \(N\) using a Lazy Segment Tree, all \(R_{\max}[l]\) values can be computed in \(O(N \log N)\).

Step 3: Offline Query Processing (Plane Sweep)

To compute \(\sum_{l=L}^R \min(R, R_{\max}[l])\), we sort queries in ascending order of right endpoint \(R\) and process them. We advance \(R\) from \(1\) to \(N\), managing the value of \(\min(R, R_{\max}[l])\) for each \(l\).

For each \(l\), the behavior of \(\min(R, R_{\max}[l])\) falls into one of two states: 1. Variable state: When \(R_{\max}[l] \geq R\), the value equals \(R\) and changes as \(R\) increases. 2. Constant state: When \(R_{\max}[l] < R\), the value is fixed at \(R_{\max}[l]\).

When \(R\) increases by \(1\), for each \(l\) that newly satisfies \(R_{\max}[l] = R - 1\), the state transitions from “variable” to “constant (value \(R-1\))”. To manage these state transitions, we prepare two Fenwick Trees:

• bit_var: Holds \(1\) if \(l\) is in variable state, \(0\) if in constant state.
• bit_const: Holds \(R_{\max}[l]\) if \(l\) is in constant state, \(0\) if in variable state.

【Query Processing Flow】 1. Loop \(R\) from \(1\) to \(N\). 2. For each \(l\) where \(R_{\max}[l] = R - 1\), update the state: - Subtract \(1\) from the \(l\)-th value of bit_var (\(1 \to 0\)). - Add \(R - 1\) to the \(l\)-th value of bit_const (\(0 \to R - 1\)). 3. For queries \([L, R]\) with right endpoint \(R\), compute the sum as follows: - \(\sum_{l=L}^R \min(R, R_{\max}[l]) = (\text{sum of } [L, R] \text{ in bit\_const}) + (\text{sum of } [L, R] \text{ in bit\_var}) \times R\) 4. Subtract the arithmetic series sum and other terms from the obtained value, and record the query answer.

---

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Coordinate compression and computing \(P_j\): \(O(N \log N)\)
  • Computing \(R_{\max}[l]\) with Lazy Segment Tree: \(O(N \log N)\)
  • Sorting queries and plane sweep with Fenwick Tree: \(O((N + Q) \log N)\)
• Space Complexity: \(O(N + Q)\)
  • The memory required for all arrays, segment tree, Fenwick Trees, and query storage is \(O(N + Q)\).

---

Implementation Notes

1. Coordinate Compression: Since the weight values \(A_i\) can be as large as \(10^9\), they cannot be directly used as BIT indices. We prepare a deduplicated and sorted array U in advance, and use binary search (lower_bound) to convert values into compact integers starting from \(1\) (coordinate compression).

2. Monoid Design for Lazy Segment Tree: For the range chmin operation to compute \(R_{\max}[l]\), we use the Atcoder Library (ACL) lazy_segtree.

   • op is defined as min(a, b) to retrieve the interval minimum.
   • mapping is defined as min(f, x) to perform chmin with the lazily propagated value.

These are defined appropriately to perform range updates correctly.

Source Code

#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;
}

---

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