次のクエリを処理できるデータ構造があれば十分です。

• 与えられた区間 \([l, r)\) について、\(x = \max_{i\in[l, r)} b_i\) を計算し、\(b_i \gets x + 1\) (\(i \in[l,r)\)) で更新する。

これを実現するには、BIT や平衡二分探索木を用いて以下のようにすればよいです。

追記

これは、以下で言及する \(d_j = 1\) なる \(j\) について、\(j \mapsto b_j\) を管理した（順序つきの）連想配列で可能です。元々この解説は、平衡二分探索木のない Python のような言語でも比較的容易に実装できる解法を探そうとして書いたので、考慮から漏れていました。以下の解法は BIT があれば可能なので、そういう言語ではうれしいと思います。

データの表現

配列 \(b\) を表現するため、値を持つ配列 \(a\) と補助の配列 \(d\) を用います。 \(j = \max_{j\le i}\,\{j\mid d_j = 1\}\) なる \(j\) を用いて \(b_i = a_j\) となるように管理します。

たとえば、

i: 0 1 2 3 4 5 6 7 8 9
a: 3 1 4 1 5 9 2 6 5 3
d: 1 0 1 0 0 0 0 1 0 0

となるとき、\(b_3 = a_2 = 4\) や \(b_7 = a_7 = 6\) となります。

与えられた \(i\) に対して \(j\) を見つけるには、\(d\) を BIT で管理したり、\(d_j = 1\) なる \(j\) を入れた平衡二分探索木 (std::set / C++) で二分探索すればよいです。

クエリ処理

最大値を求めるパートについては、\(b_l\) の値と、\(i\in[l, r)\) かつ \(d_i = 1\) なる各 \(i\) について \(a_i\) の値を計算します。それらの最大値が \(x\) です。

更新のパートでは、\(d_l \gets 1\) と \(a_l \gets x+1\) をします。\(d_r = 0\) だった場合には、\(j = \max_{j\in[l, r)}\,\{j\mid d_j = 1\}\) なる \(j\) を用いて \(a_r \gets a_j\) と \(d_r \gets 1\) で更新することで、\(b_r\) の値がこわれるのを防ぎます（\(d_r = 0\) の場合の処理は、\(a_l\) の更新より前に行います。\(j=l\) だと困るため）。

また、\(j \in (l, r)\) について \(d_j \gets 0\) で更新し、上書きされた値が無視されるようにします。

計算量解析

クエリ処理の際には、\(j \in \{l<j<r\mid d_j = 1\}\) に対して \(d_j \gets 0\) となることと、一回のクエリで \(d_j \gets 1\) となる \(j\) は高々 \(2\) 個であることから、データ構造の更新は amortized \(O(1)\) 回とわかります。

BIT や平衡二分探索木への操作はクエリあたり \(O(\log(n))\) 時間なので、\(b\) の長さを \(n\) とすると \(\langle O(n), O(\log(n))\rangle\) (amortized) となります。

この問題においては \(b\) の長さが \(W\)、クエリ回数が \(N\) なので、\(O(W+N\log(W))\) 時間となります。

ならし計算量 (amortized complexity) についての解説は https://rsk0315.hatenablog.com/entry/2022/07/22/090000 などを見るとよいかもしれません。

発展？

max に限らず、区間のモノイド積 \(x = b_l \circ b_{l+1} \circ\dots\circ b_{r-1}\) を求め、\(b_j \gets f(x)\) (\(x\in[l, r)\)) で更新するクエリを、同様の手法で \(\langle O(n), O(\log(n))\rangle\) (amortized) で処理できそうです（繰り返し二乗法由来の \(O(\log(n))\) と二分探索由来の \(O(\log(n))\) は同じ回数のはず）。

実装

• Rust, 平衡二分探索木
• Rust, セグ木
• Rust, 平衡二分探索木（追記の解法）