結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2022-05-27 23:20:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 408 ms / 3,000 ms |
コード長 | 3,643 bytes |
コンパイル時間 | 437 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 109,056 KB |
最終ジャッジ日時 | 2024-09-20 16:26:16 |
合計ジャッジ時間 | 18,059 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
class SegmentTree():# UnitXは単位元、fは区間で行いたい操作、initは自然数あるいは配列def __init__(self, init, unitX, f):self.f = f # (X, X) -> Xself.unitX = unitXself.f = fif type(init) == int:self.n = initself.n = 1 << (self.n - 1).bit_length()self.X = [unitX] * (self.n * 2)else:self.n = len(init)self.n = 1 << (self.n - 1).bit_length()# len(init)が2の累乗ではない時UnitXで埋めるself.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))# 配列のindex1まで埋めるfor i in range(self.n-1, 0, -1):self.X[i] = self.f(self.X[i*2], self.X[i*2|1])# 0-indexedのi番目の値をxで置換def update(self, i, x):# 最下段に移動i += self.nself.X[i] = x# 上向に更新i >>= 1while i:self.X[i] = self.f(self.X[i*2], self.X[i*2|1])i >>= 1# 元の配列のindexの値を見るdef getvalue(self, i):return self.X[i + self.n]# 区間[l, r)でのfを行った値def getrange(self, l, r):l += self.nr += self.nal = self.unitXar = self.unitXwhile l < r:# 左端が右子ノードであればif l & 1:al = self.f(al, self.X[l])l += 1# 右端が右子ノードであればif r & 1:r -= 1ar = self.f(self.X[r], ar)l >>= 1r >>= 1return self.f(al, ar)# Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = Falsedef max_right(self, l, z):if l >= self.n: return self.nl += self.ns = self.unitXwhile 1:while l % 2 == 0:l >>= 1if not z(self.f(s, self.X[l])):while l < self.n:l *= 2if z(self.f(s, self.X[l])):s = self.f(s, self.X[l])l += 1return l - self.ns = self.f(s, self.X[l])l += 1if l & -l == l: breakreturn self.n# Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = Falsedef min_left(self, r, z):if r <= 0: return 0r += self.ns = self.unitXwhile 1:r -= 1while r > 1 and r % 2:r >>= 1if not z(self.f(self.X[r], s)):while r < self.n:r = r * 2 + 1if z(self.f(self.X[r], s)):s = self.f(self.X[r], s)r -= 1return r + 1 - self.ns = self.f(self.X[r], s)if r & -r == r: breakreturn 0def debug(self):print("debug")print([self.getvalue(i) for i in range(min(self.n, 20))])N, M = map(int, input().split())A = list(map(int, input().split()))def f(x, y):n, p = xn_, p_ = yif n>n_:return (n,p)else:return (n_,p_)st = SegmentTree([(n, i) for i, n in enumerate(A)], (-1, -1), f)Q = int(input())for _ in range(Q):t, a, b = map(int, input().split())if t == 1:n, p = st.getvalue(a-1)st.update(a-1, (n+b, p))elif t == 2:n,p = st.getvalue(a-1)st.update(a-1, (n-b, p))else:print(st.getrange(0, M)[1]+1)