#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._size def build(self, array): assert len(array) == self._n, 'array too large' for i,v in enumerate(array, start = self._size): self._node[i] = v for 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] = value while 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_e while L < R: if L & 1: vL = self._combine_f(vL, self._node[L]); L += 1 if R & 1: R -= 1; vR = self._combine_f(self._node[R], vR) L >>= 1; R >>= 1 return self._combine_f(vL, vR) #Lazy Segment Tree class 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._size def build(self, array): assert len(array) == self._N, 'array too large' for i, v in enumerate(array, start = self._size): self._node[i] = v for 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._size for h in range(self._height, 0, -1): i = index >> h if 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_lazy def _update_from_bottom(self, index): i = (index + self._size) >> 1 while i > 0: self._node[i] = self._node_f(self._ref_lazy(i << 1), self._ref_lazy(i << 1 | 1)); i >>= 1 def update(self, Lt, Rt, value): #半開区間[Lt, Rt)に値valueを作用 if Lt == Rt: return self._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Li, Ri = Lt + self._size, Rt + self._size while Li < Ri: if Li & 1: self._lazy[Li] = self._lazy_f(self._lazy[Li], value); Li += 1 if Ri & 1: Ri -= 1; self._lazy[Ri] = self._lazy_f(self._lazy[Ri], value) Li >>= 1; Ri >>= 1 self._update_from_bottom(Lt); self._update_from_bottom(Rt - 1) def fold(self, Lt, Rt): #半開区間[Lt, Rt)の作用値を取得 if Lt == Rt: return self._e_node self._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_node while Lt < Rt: if Lt & 1: vL = self._node_f(vL, self._ref_lazy(Lt)); Lt += 1 if Rt & 1: Rt -= 1; vR = self._node_f(self._ref_lazy(Rt), vR) Lt >>= 1; Rt >>= 1 return self._node_f(vL, vR) #入力受取 N = int(input()) A = list(map(int, input().split())) Q = int(input()) query = [None] * Q for q in range(Q): t, Lt, Rt, *x = map(int, input().split()) Lt -= 1 x = 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 LIS DP = [[- N * 2] * 5 for _ in range(N + 1)] DP[0][1] = 0 for 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] = x return ans def 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 = node1 k, l, m, n, o, p, q, r, s, t = node2 A = a + k B = 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 + o F = max(e + p, max(e, f) + r) G = max(e + q, max(e, f) + s, max(e, f, g) + t) H = h + r I = max(h + s, max(h, i) + t) J = j + t return (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 ans def 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 = node1 k, l, m, n, o, p, q, r, s, t, y = node2 A = a + k B = 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 + o F = max(e + p, max(e, f) + r) G = max(e + q, max(e, f) + s, max(e, f, g) + t) H = h + r I = max(h + s, max(h, i) + t) J = j + t return (A, B, C, D, E, F, G, H, I, J, x + y) def lazy_f(lazy1, lazy2): return lazy2 K = [(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 node else: 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 ans ans = solve(N, A, Q, query) for a in ans: print(a)