結果

問題 No.2697 Range LIS Query
ユーザー navel_tosnavel_tos
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]xmax 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 == 2TLE
#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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0