結果

問題 No.2697 Range LIS Query
コンテスト
ユーザー LyricalMaestro
提出日時 2024-11-30 20:43:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 7,373 ms / 10,000 ms
コード長 5,258 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 149,952 KB
最終ジャッジ日時 2024-11-30 20:45:04
合計ジャッジ時間 66,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2279

from collections import deque

class LazySegmentTree:
    """
    非再帰版遅延セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    取得のところの都合で取得演算子は可換になっている必要がある。
    """

    def __init__(self, init_array):
        self._to_index_matrix = [
            [0, 1, 2, 3],
            [-1, 4, 5, 6],
            [-1, -1, 7, 8],
            [-1, -1, -1, 9],
        ]

        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [[0] * 10 for _ in range(2 * self.size)]
        self.lazy_array = [0 for _ in range(2 * self.size)]
        self.weight = [0 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            for j in range(4):
                for k in range(j, 4):
                    if j <= a - 1 and a - 1 <= k:
                        self.array[i + self.size][self._to_index_matrix[j][k]] = 1
            self.weight[i + self.size] = 1
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self._op(self.array[i], self.array[2 * i], self.array[2 * i + 1])
                self.weight[i] = self.weight[2 * i] + self.weight[2 * i + 1]
            end_index = start_index
            start_index = end_index // 2


    def _op(self, array, left, right):
        for  i in range(4):
            for j in range(i, 4):
                array[self._to_index_matrix[i][j]] = 0

        for  i in range(4):
            for j in range(i, 4):
                l_index = self._to_index_matrix[i][j]
                for k in range(j, 4):
                    for l in range(k, 4):
                        r_index = self._to_index_matrix[k][l]
                        index = self._to_index_matrix[i][l]
                        array[index] = max(array[index], left[l_index] + right[r_index])

    def _adjust(self, index, v):
        self.lazy_array[index] = v

        for i in range(4):
            for j in range(i, 4):
                i0 = self._to_index_matrix[i][j]
                if i <= v - 1 and v - 1 <= j:
                    self.array[index][i0] = self.weight[index]
                else:
                    self.array[index][i0] = 0

    def _propagates(self, *ids):
        for i in reversed(ids):
            self._propagate(i)

    def _propagate(self, i):
        v = self.lazy_array[i]
        if v == 0:
            return
        
        if i < self.size:
            self._adjust(2 * i, v)
            self._adjust(2 * i + 1, v)
        self.lazy_array[i] = 0

    def _get_target_index(self, l, r):
        L = l + self.size; R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while 0 < L and L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L > 0:
            yield L
            L >>= 1

    def set(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.size + l; R = self.size + r
        *ids, = self._get_target_index(l, r)
        self._propagates(*ids)
        while L < R:
            if R & 1:
                R -= 1
                self._adjust(R, x)
            if L & 1:
                self._adjust(L, x)
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            if i < self.size:
                self._op(self.array[i], self.array[2 * i], self.array[2 * i + 1])

    def get_max_length(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self._propagates(*self._get_target_index(l, r))
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        l_queue = deque()
        r_queue = deque()
        while L < R:
            if R & 1:
                R -= 1
                r_queue.appendleft(self.array[R])
            if L & 1:
                l_queue.append(self.array[L])
                L += 1
            L >>= 1; R >>= 1

        s = [0] * 10
        while len(l_queue) > 0:
            new_s = [0] * 10
            v = l_queue.popleft()
            self._op(new_s, s, v)
            s = new_s
        while len(r_queue) > 0:
            new_s = [0] * 10
            v = r_queue.popleft()
            self._op(new_s, s, v)
            s = new_s
        return s




def main():
    N = int(input())
    A = list(map(int, input().split()))

    Q = int(input())
    queries = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queries.append(values)

    
    lazy_seg_tree = LazySegmentTree(A)
    for values in queries:
        if values[0] == 1:
            _, l, r = values
            l -= 1
            r -= 1
            s = lazy_seg_tree.get_max_length(l, r + 1)
            print(max(s))
        else:
            _, l, r, x = values
            l -= 1
            r -= 1
            lazy_seg_tree.set(l, r + 1, x)






if __name__ == "__main__":
    main()
0