結果
| 問題 |
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 |
ソースコード
## 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()