結果

問題 No.2697 Range LIS Query
ユーザー navel_tosnavel_tos
提出日時 2024-03-22 22:48:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 8,619 ms / 10,000 ms
コード長 7,381 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 280,632 KB
最終ジャッジ日時 2024-03-22 22:50:03
合計ジャッジ時間 96,713 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,596 KB
testcase_01 AC 38 ms
55,596 KB
testcase_02 AC 43 ms
61,264 KB
testcase_03 AC 791 ms
93,084 KB
testcase_04 AC 716 ms
89,660 KB
testcase_05 AC 725 ms
91,080 KB
testcase_06 AC 7,739 ms
277,880 KB
testcase_07 AC 7,759 ms
277,576 KB
testcase_08 AC 7,512 ms
277,408 KB
testcase_09 AC 8,510 ms
237,284 KB
testcase_10 AC 7,926 ms
233,568 KB
testcase_11 AC 8,318 ms
239,200 KB
testcase_12 AC 4,944 ms
272,816 KB
testcase_13 AC 5,668 ms
276,656 KB
testcase_14 AC 7,077 ms
277,220 KB
testcase_15 AC 8,494 ms
280,632 KB
testcase_16 AC 8,419 ms
279,796 KB
testcase_17 AC 8,619 ms
279,540 KB
権限があれば一括ダウンロードができます

ソースコード

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]を決める直前であって、最後に採用した数字が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)
0