結果
| 問題 |
No.833 かっこいい電車
|
| コンテスト | |
| ユーザー |
 kept1994
|
| 提出日時 | 2022-05-03 01:32:55 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 539 ms / 2,000 ms |
| コード長 | 5,634 bytes |
| コンパイル時間 | 200 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 93,952 KB |
| 最終ジャッジ日時 | 2024-07-02 05:31:35 |
| 合計ジャッジ時間 | 10,099 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#!/usr/bin/env python3
import sys
MOD = 998244353
class SegTree:
def __init__(self, monoid, bottomList, func, convertLengthToThePowerOf2: bool = False):
self.monoid = monoid
self.func = func
if convertLengthToThePowerOf2:
self.actualLen = len(bottomList)
self.bottomLen = self.getSegLenOfThePowerOf2(len(bottomList))
self.offset = self.bottomLen # セグ木の最下層の最初のインデックスに合わせるためのオフセット
self.segLen = self.bottomLen * 2
self.tree = [monoid] * self.segLen
else:
self.actualLen = len(bottomList)
self.bottomLen = len(bottomList)
self.offset = self.bottomLen # セグ木の最下層の最初のインデックスに合わせるためのオフセット
self.segLen = self.bottomLen * 2
self.tree = [monoid] * self.segLen
self.build(bottomList)
"""
初期化
O(self.segLen)
"""
def build(self, seq):
# 最下段の初期化
for i, x in enumerate(seq, self.offset):
self.tree[i] = x
# ビルド
for i in range(self.offset - 1, 0, -1):
self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])
"""
直近の2べきの長さを算出
"""
def getSegLenOfThePowerOf2(self, ln: int):
if ln <= 0:
return 1
else:
import math
decimalPart, integerPart = math.modf(math.log2(ln))
return 2 ** (int(integerPart) + 1)
"""
一点加算 他演算
O(log(self.bottomLen))
"""
def pointAdd(self, i: int, val: int):
i += self.offset
self.tree[i] += val
# self.tree[i] = self.func(self.tree[i], val) <- こっちの方が都度の修正は発生しない。再帰が遅くないか次第。
while i > 1:
i >>= 1 # 2で割って頂点に達するまで下層から遡上
self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1]) # 必ず末尾0と1がペアになるのでor演算子
"""
一点更新
O(log(self.bottomLen))
"""
def pointUpdate(self, i: int, val: int):
i += self.offset
self.tree[i] = val
while i > 1:
i >>= 1 # 2で割って頂点に達するまで下層から遡上
self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1]) # 必ず末尾0と1がペアになるのでor演算子
"""
区間取得
O(log(self.bottomLen))
"""
def getRange(self, l: int, r: int):
l += self.offset
r += self.offset
vL = self.monoid
vR = self.monoid
while l < r:
if l & 1:
vL = self.func(vL, self.tree[l])
l += 1
if r & 1:
r -= 1
vR = self.func(self.tree[r], vR)
l >>= 1
r >>= 1
return self.func(vL, vR)
"""
一点取得
O(log(self.bottomLen))
"""
def getPoint(self, i: int):
i += self.offset
return self.tree[i]
"""
二分探索
O(log(self.bottomLen))
※ セグ木上の二分探索を使う場合は2べきにすること。
# !!!! ng側が返却される !!!!!
"""
def max_right(self, l, is_ok: "function"):
# print("セグ木上の二分探索を使う場合は2べきにすること。")
l += self.offset
ll = l // (l & -l) # lから始まる含む最も大きいセグメントのインデックス算出。(= 2で割れなくなるまで割る)
ans = self.monoid
while is_ok(self.func(ans, self.tree[ll])): # そのセグメントが条件を満たすかどうかの判定
ans = self.func(ans, self.tree[ll])
ll += 1
while ~ll & 1: # llの反転 ~ll = -(ll+1)
ll >>= 1 # lから始まる含む最も大きいセグメントのインデックス算出。(= 2で割れなくなるまで割る)
if ll == 1: # 最上層まで到達したら全範囲満たすということ。 → (2べきになるようにモノイド埋めする前の)実際の長さを返す。
return self.actualLen
while ll < self.offset:
ll <<= 1 # 一階層下のセグメントへ移動 (=2倍)
if is_ok(self.func(ans, self.tree[ll])): # 条件を満たすなら同一階層の隣のセグメントの下層へ。満たさないならそのまま下層へ。
ans = self.func(ans, self.tree[ll])
ll += 1
return ll - self.offset # ng側が返る
def main():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
def add(x: int, y: int):
return x + y
connect = SegTree(0, [1] * N, add, convertLengthToThePowerOf2=True)
attract = SegTree(0, A, add)
for i in range(Q):
q, x = list(map(int, input().split()))
x -= 1
if q == 1:
connect.pointUpdate(x + 1, 0)
elif q == 2:
connect.pointUpdate(x + 1, 1)
elif q == 3:
attract.pointAdd(x, 1)
else:
# xの属するグループ num
num = connect.getRange(0, x + 1)
# print(num)
# numの両端
st = connect.max_right(0, lambda x: x < num)
ed = connect.max_right(0, lambda x: x < num + 1) - 1
# print(st, ed)
res = attract.getRange(st, ed + 1)
print(res)
return
if __name__ == '__main__':
main()