結果
| 問題 |
No.880 Yet Another Segment Tree Problem
|
| ユーザー |
 あじゃじゃ
|
| 提出日時 | 2025-03-22 13:40:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,136 bytes |
| コンパイル時間 | 492 ms |
| コンパイル使用メモリ | 82,248 KB |
| 実行使用メモリ | 281,936 KB |
| 最終ジャッジ日時 | 2025-03-22 13:42:22 |
| 合計ジャッジ時間 | 32,952 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 WA * 23 TLE * 8 |
ソースコード
import sys
import math
from typing import List
BINF = 1 << 30
# セグメントツリーの各ノードの情報を表すクラス
class S:
__slots__ = ('max', 'lcm', 'sz', 'sum', 'fail', 'all_same')
def __init__(self, x: int = 0, sz: int = 1):
# コンストラクタ：引数が与えられればその値で初期化、デフォルトはゼロ（区間サイズ1）
if x == 0 and sz == 1:
self.max = 0
self.lcm = 1
self.sz = 1
self.sum = 0
self.fail = False
self.all_same = False
else:
self.max = x
self.lcm = x
self.sz = sz
self.sum = x * sz
self.fail = False
self.all_same = True
# 区間更新に用いる情報
class F:
__slots__ = ('dogcd', 'reset')
def __init__(self, dogcd: int = 0, reset: int = 0):
self.dogcd = dogcd
self.reset = reset
@staticmethod
def gcd(g: int) -> 'F':
return F(g, 0)
@staticmethod
def update(a: int) -> 'F':
return F(0, a)
def e() -> S:
return S()
def id_F() -> F:
return F()
def composition(fnew: F, fold: F) -> F:
# fnew がリセット操作なら fnew を優先、それ以外は dogcd の gcd を取る
if fnew.reset:
return fnew
return F(math.gcd(fnew.dogcd, fold.dogcd), fold.reset)
def mapping(f: F, x: S) -> S:
# すでに失敗している場合はそのまま返す
if x.fail:
return x
# リセット操作があれば値を f.reset に置き換える
if f.reset:
x = S(f.reset, x.sz)
# dogcd 操作の場合
if f.dogcd:
if x.all_same:
# 区間がすべて同じなら gcd(f.dogcd, x.max) に更新
x = S(math.gcd(f.dogcd, x.max), x.sz)
else:
# そうでなく、かつ lcm が BINF であるか、f.dogcd と x.lcm の剰余が 0 でなければ失敗扱いにする
if x.lcm == BINF or f.dogcd % x.lcm != 0:
x.fail = True
return x
def op(l: S, r: S) -> S:
# 片方の区間が空ならもう一方を返す
if r.sz == 0:
return l
if l.sz == 0:
return r
ret = S()
ret.max = max(l.max, r.max)
ret.sum = l.sum + r.sum
# lcm の計算（l.lcm または r.lcm が BINF なら BINF を返す）
# Python3.9 以降では math.lcm が使えますが、ここでは math.gcd を用います。
g = math.gcd(l.lcm, r.lcm)
lcm_val = (l.lcm * r.lcm) // g if g else 0
ret.lcm = BINF if (l.lcm >= BINF or r.lcm >= BINF or lcm_val >= BINF) else lcm_val
ret.sz = l.sz + r.sz
ret.all_same = l.all_same and r.all_same and (l.max == r.max)
ret.fail = l.fail or r.fail
return ret
class SegtreeBeats:
def __init__(self, arr: List[int]):
self._n = len(arr)
self.log = 0
self.size = 1
while self.size < self._n:
self.size *= 2
self.log += 1
self.data = [e() for _ in range(2 * self.size)]
self.lazy = [id_F() for _ in range(self.size)]
# 葉ノードの初期化
for i in range(self._n):
self.data[self.size + i] = S(arr[i], 1)
for i in range(self._n, self.size):
self.data[self.size + i] = e()
for i in range(self.size - 1, 0, -1):
self._update(i)
def _update(self, k: int):
self.data[k] = op(self.data[2 * k], self.data[2 * k + 1])
def _all_apply(self, k: int, f: F):
# segtree_beats では、apply 時に失敗フラグが立っている場合、子に伝搬して更新する
self.data[k] = mapping(f, self.data[k])
if k < self.size:
self.lazy[k] = composition(f, self.lazy[k])
# 失敗フラグが立ったら即座に子へ伝搬して更新する
if self.data[k].fail:
self._push(k)
self._update(k)
def _push(self, k: int):
self._all_apply(2 * k, self.lazy[k])
self._all_apply(2 * k + 1, self.lazy[k])
self.lazy[k] = id_F()
def prod(self, l: int, r: int) -> S:
# 区間 [l, r) のクエリ
if l == r:
return e()
l += self.size
r += self.size
# 遅延伝搬を上から下へ
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self._push(l >> i)
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
sml = e()
smr = e()
while l < r:
if l & 1:
sml = op(sml, self.data[l])
l += 1
if r & 1:
r -= 1
smr = op(self.data[r], smr)
l //= 2
r //= 2
return op(sml, smr)
def apply_point(self, p: int, f: F):
# p 番目の要素に f を適用
p += self.size
for i in range(self.log, 0, -1):
self._push(p >> i)
self.data[p] = mapping(f, self.data[p])
for i in range(1, self.log + 1):
self._update(p >> i)
def apply_range(self, l: int, r: int, f: F):
# 区間 [l, r) に f を適用する
if l == r:
return
l0 = l + self.size
r0 = r + self.size
# 上から下へ遅延伝搬
for i in range(self.log, 0, -1):
if ((l0 >> i) << i) != l0:
self._push(l0 >> i)
if ((r0 >> i) << i) != r0:
self._push((r0 - 1) >> i)
l1, r1 = l0, r0
while l0 < r0:
if l0 & 1:
self._all_apply(l0, f)
l0 += 1
if r0 & 1:
r0 -= 1
self._all_apply(r0, f)
l0 //= 2
r0 //= 2
# 下から上へ再計算
for i in range(1, self.log + 1):
if ((l1 >> i) << i) != l1:
self._update(l1 >> i)
if (((r1 - 1) >> i) << i) != (r1 - 1):
self._update((r1 - 1) >> i)
# --- 以下、標準入力の処理とクエリの実行 ---
def main():
input_data = sys.stdin.read().split()
it = iter(input_data)
N = int(next(it))
Q = int(next(it))
# 配列 A の入力（各要素は S のコンストラクタを用いて初期化）
A = [int(next(it)) for _ in range(N)]
seg = SegtreeBeats(A)
output_lines = []
for _ in range(Q):
q = int(next(it))
l = int(next(it)) - 1
r = int(next(it))
if q <= 2:
x = int(next(it))
if q == 1:
# クエリ 1: 区間の値を一括更新
seg.apply_range(l, r, F.update(x))
else:
# クエリ 2: 区間に gcd 操作を適用\n
seg.apply_range(l, r, F.gcd(x))
else:
v = seg.prod(l, r)
if q == 3:
output_lines.append(str(v.max))
elif q == 4:
output_lines.append(str(v.sum))
sys.stdout.write("\n".join(output_lines))
if __name__ == '__main__':
main()