E - 商店街の売上調査 / Shopping Street Sales Survey Editorial by admin Editorial for printing
gemini-3.5-flash-thinking概要
この問題は、商店街の店舗の売上を管理し、区間加算（操作 1）、店舗の閉店と売上の確定（操作 2）、および営業中店舗の位置に基づいた閉店済み店舗の売上合計の算出（操作 3）を高速に処理する問題です。
営業中の店舗のみに売上を加算する処理と、営業中・閉店済みの店舗の状態を効率的に管理するために、遅延評価セグメント木と 2 つの Fenwick Tree (Binary Indexed Tree, BIT) を組み合わせて解決します。
考察
1. 素朴なアプローチとその限界
各操作を愚直に配列の更新でシミュレーションすることを考えます。 - 操作 1: 範囲 \([l, r]\) の店舗をループで走査し、営業中であれば売上を \(x\) 増やす。最悪 \(O(N)\)。 - 操作 2: 店舗 \(p\) の状態を「閉店」にする。 \(O(1)\)。 - 操作 3: 営業中の店舗を左から順に数えて \(k\) 番目の店舗 \(j\) を探す（最悪 \(O(N)\)）。その後、店舗 \(1\) から \(j\) の中で閉店済みの店舗の売上を足し合わせる（最悪 \(O(N)\)）。
これでは 1 回の操作に最大 \(O(N)\) かかり、全体で \(O(QN)\) となります。 \(N, Q \le 10^5\) であるため、実行時間制限に間に合いません（TLE となります）。
2. 高速化のための 3 つのポイント
クエリを高速に処理するために、以下の 3 つの要素を導入します。
① 営業中の店舗から「左から \(k\) 番目」を高速に見つける
各店舗が「営業中なら 1、閉店なら 0」となる配列を考えます。 営業中の店舗のうち左から \(k\) 番目の店舗の番号 \(j\) は、この配列の累積和がちょうど \(k\) になるインデックスに相当します。 これは、配列の値を管理する BIT（Fenwick Tree） を用意し、その上で二分探索（BIT上の二分探索）を行うことで、\(O(\log N)\) で高速に求めることができます。
② 閉店した店舗の売上合計を高速に求める
店舗 \(i\) が閉店したときの売上を \(A_i\) とします（営業中なら \(A_i = 0\)）。 操作 3 で求めたいのは、店舗 \(1\) から \(j\) までの閉店済み店舗の売上合計、すなわち \(\sum_{i=1}^{j} A_i\) です。 これも、閉店時にその売上を記録する専用の BIT を用意しておくことで、区間和を \(O(\log N)\) で取得できます。
③ 「営業中の店舗のみ」への区間加算を高速に行う
これが最も工夫を要する部分です。
営業中の店舗のみに区間加算を行うために、遅延評価セグメント木を使用します。
セグメント木の各ノード \(u\) において、以下の情報を管理します。
- active[u]: その区間に含まれる営業中の店舗数
- sum_val[u]: その区間に含まれる営業中の店舗の売上総和
- add[u]: その区間に対する遅延加算値
区間 \([l, r]\) に \(x\) を加算する際、ノード \(u\) の区間が完全に含まれていれば、以下のように更新します。
- add[u] += x
- sum_val[u] += x * active[u]
このように、営業中の店舗数 active[u] を掛け合わせることで、閉店済みの店舗を無視して営業中の店舗だけに正しく売上を加算できます。
店舗 \(p\) が閉店する（操作 2）ときは、セグメント木上で根から葉 \(p\) までの遅延値をすべて伝播（push）させた上で、その時点での売上（葉の値）を回収します。その後、葉 \(p\) の active を 0、sum_val を 0 に更新し、親ノードへと情報をボトムアップで更新します。
アルゴリズム
遅延評価セグメント木と 2 つの BIT を用いて、以下のように各操作を処理します。
事前準備
- 遅延評価セグメント木を初期化します。
- 各店舗 \(i\) について、
activeを 1、sum_valを初期売上 \(V_i\) とします。
- 各店舗 \(i\) について、
- 営業中店舗管理用の BIT (
bit) を初期化します。- 初期状態ではすべての店舗が営業中なので、すべての位置に 1 を設定します。
- 累積閉店売上管理用の BIT (
closed_bit) を初期化します。- 初期状態ではすべて 0 です。
操作 1: 1 l r x（区間加算）
セグメント木を用いて、範囲 \([l, r]\) の active が 1 以上のノードに対して遅延加算を行います。
- 時間計算量: \(O(\log N)\)
操作 2: 2 p（店舗 \(p\) の閉店）
- セグメント木において、根から葉 \(p\) までの遅延評価を適用（
push_path）し、店舗 \(p\) の最新の売上valを取得します。 - セグメント木の葉 \(p\) の
activeを 0、sum_valを 0 に変更し、親ノードを更新します。 - 営業中店舗管理用 BIT (
bit) の位置 \(p\) から 1 を引きます（営業中から除外）。 - 累積閉店売上管理用 BIT (
closed_bit) の位置 \(p\) にvalを加算します。
- 時間計算量: \(O(\log N)\)
操作 3: 3 k（累積閉店売上の出力）
- 営業中店舗管理用 BIT (
bit) の上での二分探索（find_kth）を行い、営業中の店舗の中で左から \(k\) 番目にある店舗の番号 \(j\) を求めます。 - 累積閉店売上管理用 BIT (
closed_bit) を用いて、店舗 \(1\) から \(j\) までの合計値（closed_query(j)）を求め、出力します。
- 時間計算量: \(O(\log N)\)
計算量
時間計算量
- 初期化: \(O(N)\)
- クエリ処理:
- 操作 1: \(O(\log N)\)
- 操作 2: \(O(\log N)\)
- 操作 3: \(O(\log N)\)
- 全体: \(O((N + Q) \log N)\)
制約の \(N, Q \le 10^5\) に対して十分高速（数ミリ秒〜数百ミリ秒）に動作します。
空間計算量
- セグメント木（サイズ \(4N\) 程度）と BIT（サイズ \(N\)）を数個保持するため、\(O(N)\) です。メモリ制限に対しても非常に余裕があります。
実装のポイント
非再帰による葉へのアクセス (
push_path/deactivate_non_rec) 店舗 \(p\) の閉店処理の際、再帰を使わずに、根から葉 \(p\) までのパス上の遅延値をトップダウンで伝播させています。これにより、Python における再帰呼び出しのオーバーヘッドを減らし、高速に動作させています。BIT 上の二分探索
find_kth関数では、通常の二分探索（\(O(\log^2 N)\)）ではなく、BIT の構造を利用した \(O(\log N)\) の二分探索を実装しています。ステップ幅stepを 2 のべき乗で半分にしながら遷移することで、定数倍が非常に軽い探索を実現しています。ソースコード
import sys
sys.setrecursionlimit(300000)
def solve():
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
Q = int(input_data[1])
V = [int(x) for x in input_data[2:2+N]]
size = 1
while size < N:
size *= 2
active = [0] * (2 * size)
sum_val = [0] * (2 * size)
add = [0] * (2 * size)
for i in range(N):
active[size + i] = 1
sum_val[size + i] = V[i]
for i in range(size - 1, 0, -1):
active[i] = active[2 * i] + active[2 * i + 1]
sum_val[i] = sum_val[2 * i] + sum_val[2 * i + 1]
bit = [0] * (N + 1)
for i in range(1, N + 1):
bit[i] = i & -i
def bit_add(i, x):
while i <= N:
bit[i] += x
i += i & -i
closed_bit = [0] * (N + 1)
def closed_add(i, x):
while i <= N:
closed_bit[i] += x
i += i & -i
def closed_query(i):
s = 0
while i > 0:
s += closed_bit[i]
i -= i & -i
return s
def find_kth(k):
curr = 0
step = 1
while step * 2 <= N:
step *= 2
while step > 0:
if curr + step <= N and bit[curr + step] < k:
k -= bit[curr + step]
curr += step
step //= 2
return curr + 1
H = size.bit_length() - 1
def push_path(p):
g = size + p
for h in range(H, 0, -1):
u = g >> h
val_add = add[u]
if val_add != 0:
lc = 2 * u
rc = 2 * u + 1
if active[lc] > 0:
add[lc] += val_add
sum_val[lc] += val_add * active[lc]
if active[rc] > 0:
add[rc] += val_add
sum_val[rc] += val_add * active[rc]
add[u] = 0
def deactivate_non_rec(p):
push_path(p)
u = size + p
val = sum_val[u]
active[u] = 0
sum_val[u] = 0
add[u] = 0
u >>= 1
while u > 0:
active[u] = active[2 * u] + active[2 * u + 1]
sum_val[u] = sum_val[2 * u] + sum_val[2 * u + 1]
u >>= 1
return val
def add_range(ql, qr, x, u, l, r):
if qr <= l or r <= ql:
return
if ql <= l and r <= qr:
if active[u] > 0:
add[u] += x
sum_val[u] += x * active[u]
return
val_add = add[u]
if val_add != 0:
lc = 2 * u
rc = 2 * u + 1
if active[lc] > 0:
add[lc] += val_add
sum_val[lc] += val_add * active[lc]
if active[rc] > 0:
add[rc] += val_add
sum_val[rc] += val_add * active[rc]
add[u] = 0
mid = (l + r) // 2
add_range(ql, qr, x, 2 * u, l, mid)
add_range(ql, qr, x, 2 * u + 1, mid, r)
sum_val[u] = sum_val[2 * u] + sum_val[2 * u + 1]
out = []
ptr = 2 + N
len_data = len(input_data)
while ptr < len_data:
type_q = input_data[ptr]
if type_q == '1':
l = int(input_data[ptr+1]) - 1
r = int(input_data[ptr+2])
x = int(input_data[ptr+3])
add_range(l, r, x, 1, 0, size)
ptr += 4
elif type_q == '2':
p = int(input_data[ptr+1]) - 1
val = deactivate_non_rec(p)
bit_add(p + 1, -1)
closed_add(p + 1, val)
ptr += 2
else:
k = int(input_data[ptr+1])
j = find_kth(k)
ans = closed_query(j)
out.append(str(ans))
ptr += 2
print('\n'.join(out))
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: