結果
問題 | No.2697 Range LIS Query |
ユーザー |
![]() |
提出日時 | 2024-03-23 01:19:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 8,099 ms / 10,000 ms |
コード長 | 5,867 bytes |
コンパイル時間 | 434 ms |
コンパイル使用メモリ | 82,136 KB |
実行使用メモリ | 279,112 KB |
最終ジャッジ日時 | 2024-09-30 12:57:32 |
合計ジャッジ時間 | 75,353 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
import sysinput = sys.stdin.readlineclass LazySegmentTree:def __init__(self,n,identity_e_node,identity_e_lazy,combine_node_f,combine_lazy_f,reflect_f,):self._n = nself._size = 1self._height = 0while self._size < self._n:self._size <<= 1self._height += 1self._identity_e_node = identity_e_nodeself._identity_e_lazy = identity_e_lazyself._combine_node_f = combine_node_fself._combine_lazy_f = combine_lazy_fself._reflect_f = reflect_fself._node = [self._identity_e_node] * (2 * self._size)self._lazy = [self._identity_e_lazy] * (2 * self._size)# 遅延データの値を値データに反映させたときの値を返す。def _reflect_lazy(self, index):return self._reflect_f(self._node[index], self._lazy[index])def _propagate_from_top(self, index):index += self._sizefor h in range(self._height, 0, -1):i = index >> hif self._lazy[i] != self._identity_e_lazy:self._lazy[i << 1] = self._combine_lazy_f(self._lazy[i << 1], self._lazy[i])self._lazy[i << 1 | 1] = self._combine_lazy_f(self._lazy[i << 1 | 1], self._lazy[i])self._node[i] = self._reflect_lazy(i)self._lazy[i] = self._identity_e_lazydef _update_from_bottom(self, index):index = (index + self._size) >> 1while index:self._node[index] = self._combine_node_f(self._reflect_lazy(index << 1),self._reflect_lazy(index << 1 | 1))index >>= 1def build(self, array):assert len(array) == self._nfor index, value in enumerate(array, start=self._size):self._node[index] = valuefor index in range(self._size - 1, 0, -1):self._node[index] = self._combine_node_f(self._node[index << 1],self._node[index << 1 | 1])# 区間更新 位置[L, R) (0-indexed)を値valueで更新def update(self, L, R, value):self._propagate_from_top(L)self._propagate_from_top(R - 1)L_lazy = L + self._sizeR_lazy = R + self._sizewhile L_lazy < R_lazy:if L_lazy & 1:self._lazy[L_lazy] = self._combine_lazy_f(self._lazy[L_lazy], value)L_lazy += 1if R_lazy & 1:R_lazy -= 1self._lazy[R_lazy] = self._combine_lazy_f(self._lazy[R_lazy], value)L_lazy >>= 1R_lazy >>= 1self._update_from_bottom(L)self._update_from_bottom(R - 1)# 区間取得 区間[L, R) (0-indexed)内の要素について# L番目から順にcombine_node_fを適用した値を返す。def fold(self, L, R):self._propagate_from_top(L)self._propagate_from_top(R - 1)L += self._sizeR += self._sizevalue_L = self._identity_e_nodevalue_R = self._identity_e_nodewhile L < R:if L & 1:value_L = self._combine_node_f(value_L, self._reflect_lazy(L))L += 1if R & 1:R -= 1value_R = self._combine_node_f(self._reflect_lazy(R), value_R)L >>= 1R >>= 1return self._combine_node_f(value_L, value_R)def __str__(self):temp = []for i in range(self._n):temp.append(str(self.fold(i, i + 1)))return ' '.join(temp)def combine_lazy_f(lhs, rhs):if rhs == -1:return lhsreturn rhsdef reflect_f(node, lazy):if lazy == -1:return nodec = [0] * 11for i in range(10):c[i] = lazy[i] * node[-1]c[-1] = node[-1]return cN = int(input())A = list(map(int, input().split()))def f(a):L = [0] * 11if a == 1:L[0] = 1elif a == 2:L[4] = 1elif a == 3:L[7] = 1else:L[9] = 1L[-1] = 1return Ldef op(a, b):c = [0] * 11# 11 -> 11c[0] = a[0] + b[0]# 11 -> 12, 11 -> 22, 12 -> 22c[1] = max(a[0] + b[1], a[0] + b[4], a[1] + b[4])# 11 -> 13, 11 -> 23, 11 -> 33,# 12 -> 23, 12 -> 33,# 13 -> 33c[2] = max(a[0] + b[2], a[0] + b[5], a[0] + b[7],a[1] + b[5], a[1] + b[7], a[2] + b[7])# 11 -> 14, 11 -> 24, 11 -> 34, 11 -> 44# 12 -> 24, 12 -> 34, 12 -> 44# 13 -> 34, 13 -> 44, 14 -> 44c[3] = max(a[0] + b[3], a[0] + b[6], a[0] + b[8], a[0] + b[9],a[1] + b[6], a[1] + b[8], a[1] + b[9],a[2] + b[8], a[2] + b[9], a[3] + b[9])# 22 -> 22c[4] = a[4] + b[4]# 22 -> 23, 22 -> 33, 23 -> 33c[5] = max(a[4] + b[5], a[4] + b[7], a[5] + b[7])# 22 -> 24, 22 -> 34, 22 -> 44# 23 -> 34, 23 -> 44, 24 -> 44c[6] = max(a[4] + b[6], a[4] + b[8], a[4] + b[9],a[5] + b[8], a[5] + b[9], a[6] + b[9])# 33 -> 33c[7] = a[7] + b[7]# 33 -> 34, 33 -> 44, 34 -> 44c[8] = max(a[7] + b[8], a[7] + b[9], a[8] + b[9])# 44 -> 44c[9] = a[9] + b[9]c[10] = a[10] + b[10]return cD = list(map(f, A))T = LazySegmentTree(N,[0] * 11,-1,op,combine_lazy_f,reflect_f)T.build(D)Q = int(input())for _ in range(Q):q = list(map(int, input().split()))if q[0] == 1:l, r = q[1:]print(max(T.fold(l - 1, r)[:-1]))else:l, r, x = q[1:]L = f(x)T.update(l - 1, r, L)