結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-03-01 17:36:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 973 ms / 2,000 ms |
コード長 | 3,148 bytes |
コンパイル時間 | 389 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 123,096 KB |
最終ジャッジ日時 | 2024-06-22 18:52:02 |
合計ジャッジ時間 | 10,965 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
"""g(f(a, b), c) = f(g(a, c), g(b, c))...cを後から作用させても、先に作用させても結果は同じ。(両方に作用させることに注意)g(g(a, b), c) = g(a, h(b, c))...b, cを順番に作用させることはh(b,c)を一回作用させることと同じ。(計算の省略が可能)例)例えば区間の最大値を求める + 区間を変更するというクエリではf(a, b) = max(a, b) (単位元は0)g(a, c) = c(ただしc = 0ならばa)g = h今回は区間に対してはなにもしない + 区間を変更するというクエリである。したがってf(a, b) = 0g(a, c) = c(ただしc = 0ならばa)g = hとすれば良い。(最下段はfの影響を受けない。)"""class segtree:def __init__(self, n, L = None):self.raw_len = nself.list = Lself.init()def init(self):N = 1n = self.raw_lenwhile N < n:N *= 2self.len = Nself.node = [0]*(2*N-1)self.lazy = [0]*(2*N-1)if self.list:for i in range(self.raw_len):self.node[i+self.len-1] = self.list[i]for i in range(self.len - 2, -1, -1):self.node[i] = 0def update(self, i, x):#点更新i += self.len - 1self.node[i] = xwhile i > 0:i = (i-1)//2self.node[i] = 0def eval(self, k):if self.lazy[k] != 0:self.node[k] = self.lazy[k]if k < self.len - 1:#要編集。和なら半数伝播、minmaxなら全数伝播。self.lazy[2*k+1] = self.lazy[k]self.lazy[2*k+2] = self.lazy[k]self.lazy[k] = 0def range_update(self, a, b, x, k=0, l=0, r=None):if r == None:r = self.lenself.eval(k)if r <= a or b <= l:return 0if a <= l and r <= b:self.lazy[k] = x #max,minなら(r-l)は書かなくて良いself.eval(k)else:self.range_update(a, b, x, k*2+1, l, (l+r)//2)self.range_update(a, b, x, k*2+2, (l+r)//2, r)self.node[k] = 0def query(self, a, b, k = 0, l = 0, r = None):if r == None:r = self.lenif r <= a or b <= l:return 0self.eval(k, l, r)if a <= l and r <= b:return self.node[k]else:vl = self.query(a, b, k*2+1, l, (l+r)//2)vr = self.query(a, b, k*2+2, (l+r)//2, r)return 0def nodes(self):for i in range(2*self.len-1):self.eval(i)res = self.node[self.len-1:]return list(res)N = int(input())a = [int(i) for i in input().split()]dr = {} #数numのうち最も右にあるものはdr[num]dl = {}for i, num in enumerate(a):dr[num] = iar = a[::-1]for i, num in enumerate(ar):dl[num] = N-1-iseg = segtree(N)for num, _ in sorted(dr.items()):l = dl[num]r = dr[num]seg.range_update(l, r+1, num)ans = seg.nodes()ans = [str(i) for i in ans if i]print(" ".join(ans))