区間 \([l,r]\) が安定配置であることは、\(A_l=\min_{l\leq i\leq r}A_i\) であることと同値です。（最小値が \(l\) にあるとき条件を満たすのは明らかです。そうでないとき、最小値を達成する添字 \(j\) が条件を満たしません）

各 \(i\) に対し、 区間 \([i,r]\) が安定配置となる最大の \(r\) を\(B_i\) とします。単調スタックを用いることで全ての \(B_i\) を \(O(N)\) で求めることができます。

クエリ \([L,R]\) に対する答は

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

となります。シグマの部分を高速に計算する方法を考えます。

\(B'_{i,R}=\begin{cases} B_i & B_i<Rのとき\\ 0 & B_i\geq Rのとき \end{cases}\)

\(C_{i,R}=\begin{cases} 0 & B_i<Rのとき\\ 1 & B_i\geq Rのとき \end{cases}\)

と定めます。このとき、

\(\sum_{i=L}^{R}\min(R,B_i)=R\sum_{i=L}^{R}C_{i,R}+\sum_{i=L}^{R}B'_{i,R}\)

となります。また、 \(R\) を単調に変化させるとき、その過程で \(B',C\) の各要素の変更は高々 1 回しか起こりません。

よって、 \(B',C\) をセグメントツリーなどで管理しながら、クエリを先読みして \(R\) の昇順に処理することにより、全体で \(O((N+Q)\log N)\) でこの問題を解くことができます。

実装例 (C++)

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

long long op(long long x, long long y){ return x + y; }
long long e(){ return 0; }

int main(){
  int n, q;
  cin >> n >> q;
  vector<int> a(n+1);
  for(int i=0; i<n; i++) cin >> a[i];
  a[n] = -1;

  vector<int> b(n);
  vector<int> st;
  for(int i=0; i<n+1; i++){
    while(st.size() > 0 && a[st.back()] > a[i]){
      b[st.back()] = i - 1;
      st.pop_back();
    }
    st.push_back(i);
  }

  vector<array<int, 3>> query;
  for(int i=0; i<q; i++){
    int l, r;
    cin >> l >> r;
    query.push_back({r-1, l-1, i});
  }
  sort(query.begin(), query.end());

  vector<array<int, 2>> bi(n);
  for(int i=0; i<n; i++){
    bi[i] = {b[i], i};
  }
  sort(bi.begin(), bi.end());

  atcoder::segtree<long long, op, e> seg_b(n), seg_c(vector<long long>(n, 1));
  vector<long long> ans(q);
  int pos = 0;
  for(auto[r, l, i]: query){
    while(pos < n && bi[pos][0] < r){
      seg_b.set(bi[pos][1], bi[pos][0]);
      seg_c.set(bi[pos][1], 0);
      pos++;
    }
    ans[i] = r*seg_c.prod(l,r+1) + seg_b.prod(l,r+1) - (long long)(r-l+1)*(r+l-2)/2;
  }

  for(int i=0; i<q; i++) cout << ans[i] << endl;
}

実装例 (Python)

import operator
from atcoder.segtree import SegTree

N, Q = map(int, input().split())
A = list(map(int, input().split())) + [-1]

B = [0] * N
st = []
for i in range(N+1):
  while len(st) > 0 and A[st[-1]] > A[i]:
    L = st.pop()
    B[L] = i - 1
  st.append(i)

BI=[(b, i) for i,b in enumerate(B)]
BI.sort()

query = []
for i in range(Q):
  L, R = map(int, input().split())
  query.append((R-1, L-1, i))
query.sort()

seg_B = SegTree(operator.add, 0, N)
seg_C = SegTree(operator.add, 0, [1]*N)
ans = [0]*Q
pos = 0
for R, L, i in query:
  while pos < N and BI[pos][0] < R:
    seg_B.set(BI[pos][1], BI[pos][0])
    seg_C.set(BI[pos][1], 0)
    pos += 1
  ans[i] = R*seg_C.prod(L,R+1) + seg_B.prod(L,R+1) - (R-L+1)*(R+L-2)//2

print(*ans, sep="\n")