定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

Slido

以下のリンクから匿名発言が出来ます．質問だけじゃなく実況なども気軽にしてください．

QR Code for Acompany競プロ勉強会18.png

$N$ 個組みの対象を $B$ 個組みのブロック $N/B$ 個に分割して，ブロックごとに処理することで計算量を抑えられる問題は非常に多い．

特に $B=\sqrt{N}$ など，ブロックサイズとして平方根を用いることが多く，このような時には「平方分割」と呼ばれる．ただし $B$ として適切な値は必ずしもちょうど $\sqrt{N}$ とは限らないので，実行時間が厳しい場合などは適宜丁寧に $B$ の値を見極める必要がある．

想定解が平方分割の問題はそんなに多くないが，（速い言語なら）様々な問題を非想定解として通すことができる．

長さ $N$ の数列を長さ $B$ ごとに分割することで計算量を抑える．

<aside> ❓ 長さ $N$ の数列 $a=(a_0,\dots,a_{N-1})$ が与えられる． $Q$ 個のクエリに順に答える．クエリは以下の2種類

更新クエリ $(i,x)$ : $a_i$ の値を $x$ に変更取得クエリ $(l,r)$ : $a_l, \dots, a_{r-1}$ の最大値を出力

$1\leq N,Q\leq 10^5$

</aside>

愚直解だと $\Theta(NQ)$ 時間かかる．

セグメント木を用いることで $\Theta(N + Q\log N)$ 時間で解くことが出来るが，ここではブロック分割による解法を紹介する．

以下の図のように数列を $B$ 個ごとに区切り，各ブロックの最大値を計算しておく．