問題
長さ $N$ の非負整数列 $A_1, A_2, \ldots, A_N$ に対し、以下の $Q$ クエリをオンラインで処理せよ。
- クエリ
1 l r: $A_l, A_{l+1}, \ldots, A_r$ の各要素を $\lfloor \sqrt{A_i} \rfloor$ に置き換える - クエリ
2 l r: $\displaystyle\sum_{i=l}^{r} A_i$ を出力する
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| $Q$ | $1 \le Q \le 10^5$ |
| $A_i$ | $0 \le A_i \le 10^{18}$ |
| クエリ形式 | t l r（1-indexed, $l \le r$） |
入出力例
入力例 1
4 3
100 100 100 100
2 1 4
1 1 4
2 1 4出力例 1
400
40初期和 = 400。区間 [1,4] を $\lfloor\sqrt{\cdot}\rfloor$ で更新: $100 \to 10$。和 = 40。
概念図: 平方分割 + 収束スキップ
ヒント（段階的開示）
ヒント1: 方向性
$\lfloor\sqrt{x}\rfloor$ の繰り返し適用は急速に収束する（$10^{18}$ は高々 6 回で 1 になる）。
「全要素が既に 0/1 に収束済み」のブロックは更新をスキップできる。
この収束性を利用した平方分割が効率的。
ヒント2: アプローチ
- ブロックサイズ $B \approx \sqrt{N}$ で分割
- 各ブロックは「和
sum」と「最大値max」を管理 - 更新クエリ:
block_max[b] <= 1ならスキップ - それ以外は各要素を直接
isqrtで更新し、ブロック統計を再計算 - 計算量: $O((N + Q) \sqrt{N} \cdot \alpha)$、$\alpha \le 6$
ヒント3: コード骨格
B = 320 # ブロックサイズ ≈ sqrt(N)
# 更新関数
def update(l, r): # 0-indexed, inclusive
for b in range(l // B, r // B + 1):
if block_max[b] <= 1:
continue # 収束済み → スキップ
lo, hi = b * B, min((b+1) * B, N)
al, ar = max(lo, l), min(hi - 1, r)
for i in range(al, ar + 1):
A[i] = isqrt(A[i])
# ブロック統計を再計算
block_sum[b] = sum(A[lo:hi])
block_max[b] = max(A[lo:hi])模範解答 (Python)
import sys, math
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = max(1, int(N**0.5))
n_blocks = (N + B - 1) // B
block_sum = [0] * n_blocks
block_max = [0] * n_blocks
for i, v in enumerate(A):
b = i // B
block_sum[b] += v
if v > block_max[b]:
block_max[b] = v
def rebuild(b):
lo = b * B
hi = min(lo + B, N)
block_sum[b] = sum(A[lo:hi])
block_max[b] = max(A[lo:hi]) if hi > lo else 0
def update(l, r):
for b in range(l // B, r // B + 1):
if block_max[b] <= 1:
continue
lo = b * B
hi = min(lo + B, N)
al = max(lo, l)
ar = min(hi - 1, r)
changed = False
for i in range(al, ar + 1):
nv = math.isqrt(A[i])
if nv != A[i]:
A[i] = nv
changed = True
if changed:
rebuild(b)
def query_sum(l, r):
res = 0
for b in range(l // B, r // B + 1):
lo = b * B
hi = min(lo + B, N)
al = max(lo, l)
ar = min(hi - 1, r)
if al == lo and ar == hi - 1:
res += block_sum[b]
else:
for i in range(al, ar + 1):
res += A[i]
return res
out = []
for _ in range(Q):
line = input().split()
t, l, r = int(line[0]), int(line[1]) - 1, int(line[2]) - 1
if t == 1:
update(l, r)
else:
out.append(str(query_sum(l, r)))
sys.stdout.write('\n'.join(out) + ('\n' if out else ''))
solve()Step-by-Step 解説
Step 1: 平方分割の設計
配列をサイズ $B \approx \sqrt{N}$ のブロックに分割し、各ブロックで「和」と「最大値」を管理する。最大値が $\le 1$ なら全要素が 0 か 1 に収束している。
Step 2: 収束スキップによる高速化
block_max[b] <= 1 のブロックは更新を完全にスキップ。$10^{18}$ に対して平方根の繰り返し適用は高々 6 回で収束するため、各要素の更新回数は $O(\log \log A_{max})$ 回に限られる。
Step 3: 和クエリ
完全ブロックは block_sum[b] を使い $O(1)$、端数部分は線形走査。全体 $O(\sqrt{N})$ per クエリ。
Step 4: 計算量解析
各要素の総更新回数は $O(N \log\log A_{max})$。和クエリは $O(Q\sqrt{N})$。全体 $O(N \log\log A_{max} + Q\sqrt{N})$。
計算量
| 処理 | 計算量 |
|---|---|
| 前処理 | $O(N)$ |
| 更新クエリ（全体） | $O(N \log\log A_{max})$ amortized |
| 和クエリ 1回 | $O(\sqrt{N})$ |
| 全体 | $O(N \log\log A_{max} + Q\sqrt{N})$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
block_max 更新忘れ | rebuild を呼ばない | 要素変更後に必ず rebuild(b) を呼ぶ |
| 端ブロックの境界 | al, ar の計算誤り | al = max(lo, l), ar = min(hi-1, r) |
収束判定が max==0 のみ | 1 も収束済み | block_max[b] <= 1 でスキップ |
Python の isqrt 精度 | 自前実装では浮動小数点誤差 | math.isqrt(x) を使用 |
次のステップ
- 発展: 区間 $\lfloor A_i / k \rfloor$ 更新 + 和クエリ（同様の収束性を利用）
- 類題: Codeforces 438D "The Child and Sequence"（区間 mod + 和クエリ）
- 応用: 区間 GCD 更新（GCD も同様に急速収束）
自己評価
自分の回答:
気づき・メモ: