結果
| 問題 |
No.749 クエリ全部盛り
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-26 15:51:00 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,330 bytes |
| コンパイル時間 | 277 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 847,716 KB |
| 最終ジャッジ日時 | 2025-03-26 15:52:04 |
| 合計ジャッジ時間 | 10,050 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 MLE * 1 -- * 4 |
ソースコード
MOD = 10**9 + 7
def main():
import sys
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr]); ptr += 1
Q = int(input[ptr]); ptr += 1
# Precompute Fibonacci numbers and their prefix sums
F = [0] * (N)
S_F = [0] * (N)
if N >= 1:
F[0] = 0
S_F[0] = 0
if N >= 2:
F[1] = 1
S_F[1] = 1
for i in range(2, N):
F[i] = (F[i-1] + F[i-2]) % MOD
for i in range(1, N):
if i == 1:
S_F[i] = F[i]
else:
S_F[i] = (S_F[i-1] + F[i]) % MOD
class LazySegmentTree:
def __init__(self, size):
self.n = size
self.size = 1
while self.size < self.n:
self.size <<= 1
self.tree = [ {'sum_a':0, 'mul':1, 'add':0, 'fib_add':0} for _ in range(2 * self.size) ]
def push(self, node, l, r):
if node >= self.size:
return
current = self.tree[node]
mul = current['mul']
add = current['add']
fib_add = current['fib_add']
if mul == 1 and add == 0 and fib_add == 0:
return
left = 2 * node
right = 2 * node + 1
mid = (l + r) // 2
len_left = mid - l + 1
sum_F_left = (S_F[mid] - (S_F[l-1] if l > 0 else 0)) % MOD if mid < self.n else 0
self.tree[left]['sum_a'] = (
mul * self.tree[left]['sum_a'] +
add * len_left +
fib_add * sum_F_left
) % MOD
self.tree[left]['mul'] = (mul * self.tree[left]['mul']) % MOD
self.tree[left]['add'] = (mul * self.tree[left]['add'] + add) % MOD
self.tree[left]['fib_add'] = (mul * self.tree[left]['fib_add'] + fib_add) % MOD
len_right = r - (mid + 1) + 1
rr = min(r, self.n - 1)
sum_F_right = (S_F[rr] - (S_F[mid] if mid + 1 <= rr else 0)) % MOD if mid + 1 < self.n else 0
self.tree[right]['sum_a'] = (
mul * self.tree[right]['sum_a'] +
add * len_right +
fib_add * sum_F_right
) % MOD
self.tree[right]['mul'] = (mul * self.tree[right]['mul']) % MOD
self.tree[right]['add'] = (mul * self.tree[right]['add'] + add) % MOD
self.tree[right]['fib_add'] = (mul * self.tree[right]['fib_add'] + fib_add) % MOD
self.tree[node]['mul'] = 1
self.tree[node]['add'] = 0
self.tree[node]['fib_add'] = 0
def range_update(self, a, b, mul_val, add_val, fib_val):
stack = [(1, 0, self.size - 1, False)]
while stack:
node, l, r, processed = stack.pop()
if not processed:
if b < l or a > r:
continue
if a <= l and r <= b:
len_seg = r - l + 1
rr = min(r, self.n - 1)
sum_F_seg = (S_F[rr] - (S_F[l-1] if l > 0 else 0)) % MOD if l < self.n else 0
self.tree[node]['sum_a'] = (
mul_val * self.tree[node]['sum_a'] +
add_val * len_seg +
fib_val * sum_F_seg
) % MOD
self.tree[node]['mul'] = (mul_val * self.tree[node]['mul']) % MOD
self.tree[node]['add'] = (mul_val * self.tree[node]['add'] + add_val) % MOD
self.tree[node]['fib_add'] = (mul_val * self.tree[node]['fib_add'] + fib_val) % MOD
continue
self.push(node, l, r)
mid = (l + r) // 2
stack.append((node, l, r, True))
stack.append((2 * node + 1, mid + 1, r, False))
stack.append((2 * node, l, mid, False))
else:
left = 2 * node
right_node = 2 * node + 1
self.tree[node]['sum_a'] = (self.tree[left]['sum_a'] + self.tree[right_node]['sum_a']) % MOD
def range_query(self, a, b):
res = 0
stack = [(1, 0, self.size - 1)]
while stack:
node, l, r = stack.pop()
if b < l or a > r:
continue
if a <= l and r <= b:
res = (res + self.tree[node]['sum_a']) % MOD
continue
self.push(node, l, r)
mid = (l + r) // 2
stack.append((2 * node + 1, mid + 1, r))
stack.append((2 * node, l, mid))
return res
lst = LazySegmentTree(N)
for _ in range(Q):
q = int(input[ptr]); ptr +=1
l = int(input[ptr]); ptr +=1
r = int(input[ptr]); ptr +=1
k = int(input[ptr]); ptr +=1
if q == 0:
sum_val = lst.range_query(l, r)
print((sum_val * k) % MOD)
elif q == 1:
lst.range_update(l, r, 0, k, 0)
elif q == 2:
lst.range_update(l, r, 1, k, 0)
elif q == 3:
lst.range_update(l, r, k, 0, 0)
elif q == 4:
lst.range_update(l, r, 1, 0, k)
if __name__ == '__main__':
main()