結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:48:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 7,412 ms / 10,000 ms |
コード長 | 7,381 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 280,720 KB |
最終ジャッジ日時 | 2024-09-30 12:15:44 |
合計ジャッジ時間 | 77,218 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#yukicoder423G Range LIS Query#Segment Tree: O(logN)class SegmentTree:def __init__(self, n, identity_e, combine_f): self._n = n; self._size = 1 << (n-1).bit_length(); self._identity_e = identity_e; self._combine_f =combine_f; self._node = [self._identity_e] * 2 * self._sizedef build(self, array):assert len(array) == self._n, 'array too large'for i,v in enumerate(array, start = self._size): self._node[i] = vfor i in range(self._size - 1, 0, -1): self._node[i] = self._combine_f(self._node[i<<1|0], self._node[i<<1|1])def update(self, index, value): #一点更新i = self._size + index; self._node[i] = valuewhile i - 1: i >>= 1; self._node[i] = self._combine_f(self._node[i<<1|0], self._node[i<<1|1])def fold(self, L, R): #区間取得: [L,R)の区間値を得るL += self._size; R += self._size; vL = vR = self._identity_ewhile L < R:if L & 1: vL = self._combine_f(vL, self._node[L]); L += 1if R & 1: R -= 1; vR = self._combine_f(self._node[R], vR)L >>= 1; R >>= 1return self._combine_f(vL, vR)#Lazy Segment Treeclass LazySegmentTree:#適応条件: 値X, 遅延Lが (1)モノイド (2)単位元 (3)結合法則 (4)右作用可能def __init__(self, N, e_node, e_lazy, node_f, lazy_f, ref_f): self._N = N; self._height = (N - 1).bit_length(); self._size = 1 << self._height;self._e_node = e_node; self._e_lazy = e_lazy; self._node_f = node_f; self._lazy_f = lazy_f; self._ref_f = ref_f; self._node = [e_node] * 2 *self._size; self._lazy = [e_lazy] * 2 * self._sizedef build(self, array):assert len(array) == self._N, 'array too large'for i, v in enumerate(array, start = self._size): self._node[i] = vfor i in range(self._size - 1, 0, -1): self._node[i] = self._node_f(self._node[i << 1], self._node[i << 1 | 1])def _ref_lazy(self, index): return self._ref_f(self._node[index], self._lazy[index])def _propagate_from_top(self, index): #遅延評価・子へのpush 唯一遅延をresetする関数index += self._sizefor h in range(self._height, 0, -1):i = index >> hif self._lazy[i] != self._e_lazy: Lt, Rt = i << 1, i << 1 | 1; self._lazy[Lt] = self._lazy_f(self._lazy[Lt], self._lazy[i]); self._lazy[Rt] = self._lazy_f(self._lazy[Rt], self._lazy[i]); self._node[i] = self._ref_lazy(i); self._lazy[i] = self._e_lazydef _update_from_bottom(self, index):i = (index + self._size) >> 1while i > 0: self._node[i] = self._node_f(self._ref_lazy(i << 1), self._ref_lazy(i << 1 | 1)); i >>= 1def update(self, Lt, Rt, value): #半開区間[Lt, Rt)に値valueを作用if Lt == Rt: returnself._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Li, Ri = Lt + self._size, Rt + self._sizewhile Li < Ri:if Li & 1: self._lazy[Li] = self._lazy_f(self._lazy[Li], value); Li += 1if Ri & 1: Ri -= 1; self._lazy[Ri] = self._lazy_f(self._lazy[Ri], value)Li >>= 1; Ri >>= 1self._update_from_bottom(Lt); self._update_from_bottom(Rt - 1)def fold(self, Lt, Rt): #半開区間[Lt, Rt)の作用値を取得if Lt == Rt: return self._e_nodeself._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Lt, Rt = Lt + self._size, Rt + self._size; vL, vR = self._e_node, self._e_nodewhile Lt < Rt:if Lt & 1: vL = self._node_f(vL, self._ref_lazy(Lt)); Lt += 1if Rt & 1: Rt -= 1; vR = self._node_f(self._ref_lazy(Rt), vR)Lt >>= 1; Rt >>= 1return self._node_f(vL, vR)#入力受取N = int(input())A = list(map(int, input().split()))Q = int(input())query = [None] * Qfor q in range(Q):t, Lt, Rt, *x = map(int, input().split())Lt -= 1x = 0 if t == 1 else x[0]query[q] = (t, Lt, Rt, x)#愚直解def brute(N, A, Q, query):A = A[:]ans = []for t, Lt, Rt, x in query:if t == 1:B = A[Lt: Rt]N = len(B)#DP[i][x]: B[i]を決める直前であって、最後に採用した数字がxのmax LISDP = [[- N * 2] * 5 for _ in range(N + 1)]DP[0][1] = 0for i, b in enumerate(B):for x in range(1, 5):DP[i + 1][x] = DP[i][x]for x in range(1, b + 1):DP[i + 1][b] = max(DP[i + 1][b], DP[i][x] + 1)ans.append(max(DP[-1]))if t == 2:for i in range(Lt, Rt):A[i] = xreturn ansdef solve_TLE(N, A, Q, query):#一点更新SegTreeを使う。t == 2のクエリでTLEする#node: 区間内のLIS (1 - 1/2/3/4, 2 - 2/3/4, 3 - 3/4, 4 - 4)def node_f(node1, node2):a, b, c, d, e, f, g, h, i, j = node1k, l, m, n, o, p, q, r, s, t = node2A = a + kB = max(a + l, max(a, b) + o)C = max(a + m, max(a, b) + p, max(a, b, c) + r)D = max(a + n, max(a, b) + q, max(a, b, c) + s, max(a, b, c, d) + t)E = e + oF = max(e + p, max(e, f) + r)G = max(e + q, max(e, f) + s, max(e, f, g) + t)H = h + rI = max(h + s, max(h, i) + t)J = j + treturn (A, B, C, D, E, F, G, H, I, J)ST = SegmentTree(N, (0, 0, 0, 0, 0, 0, 0, 0, 0, 0), node_f)K = [(1, 0, 0, 0, 0, 0, 0, 0, 0, 0),(0, 0, 0, 0, 1, 0, 0, 0, 0, 0),(0, 0, 0, 0, 0, 0, 0, 1, 0, 0),(0, 0, 0, 0, 0, 0, 0, 0, 0, 1)]ST.build([K[a - 1] for a in A])ans = []for t, Lt, Rt, x in query:if t == 1:ans.append( max(ST.fold(Lt, Rt)) )if t == 2:k = K[x - 1]for i in range(Lt, Rt):ST.update(i, k)return ansdef solve(N, A, Q, query):#遅延セグ木を使う node_fは長さ情報を追加#node: 区間内のLIS (1 - 1/2/3/4, 2 - 2/3/4, 3 - 3/4, 4 - 4, 長さ)def node_f(node1, node2):a, b, c, d, e, f, g, h, i, j, x = node1k, l, m, n, o, p, q, r, s, t, y = node2A = a + kB = max(a + l, max(a, b) + o)C = max(a + m, max(a, b) + p, max(a, b, c) + r)D = max(a + n, max(a, b) + q, max(a, b, c) + s, max(a, b, c, d) + t)E = e + oF = max(e + p, max(e, f) + r)G = max(e + q, max(e, f) + s, max(e, f, g) + t)H = h + rI = max(h + s, max(h, i) + t)J = j + treturn (A, B, C, D, E, F, G, H, I, J, x + y)def lazy_f(lazy1, lazy2):return lazy2K = [(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1),(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1),(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1)]def ref_f(node, lazy):if lazy == 0:return nodeelse:base = K[lazy - 1]dist = node[-1]return tuple(i * dist for i in base)LST = LazySegmentTree(N, tuple([0] * 11), 0, node_f, lazy_f, ref_f)LST.build([K[a - 1] for a in A])ans = []for t, Lt, Rt, x in query:if t == 1:ans.append( max(LST.fold(Lt, Rt)[:-1]) )if t == 2:LST.update(Lt, Rt, x)return ansans = solve(N, A, Q, query)for a in ans:print(a)