結果

問題 No.1234 典型RMQ
ユーザー anagohirameanagohirame
提出日時 2020-09-19 03:21:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,336 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 86,916 KB
実行使用メモリ 171,112 KB
最終ジャッジ日時 2023-09-27 06:52:02
合計ジャッジ時間 5,270 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 65 ms
71,288 KB
testcase_02 AC 68 ms
71,276 KB
testcase_03 WA -
testcase_04 AC 67 ms
71,592 KB
testcase_05 AC 67 ms
71,348 KB
testcase_06 TLE -
testcase_07 WA -
testcase_08 TLE -
testcase_09 WA -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 TLE -
testcase_17 WA -
testcase_18 WA -
testcase_19 TLE -
testcase_20 AC 1,683 ms
101,112 KB
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 68 ms
71,244 KB
testcase_28 AC 67 ms
71,480 KB
testcase_29 AC 69 ms
71,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class LazySegTree():
	def __init__(self, a, func, unit, oper, comp, idem):
		#the number of nodes is 2n-1
		self.hght = len(a).bit_length()
		self.n = 1 << self.hght
		self.size = len(a)
		self.func = func #(ele, ele) -> ele
		self.unit = unit #ele
		self.oper = oper #(ele, op) -> ele
		self.comp = comp #(op, op) -> op
		self.idem = idem #op
		self.node = [unit] * (2 * self.n)
		#immediate evaluation enables size reduction
		self.lazy = [idem] * self.n
		for i in range(self.size + self.n - 1, 0, -1):
			if i >= self.n:
				self.node[i] = a[i - self.n]
			else:
				self.update(i)

	def update(self, k):
		self.node[k] = self.func(self.node[2 * k], self.node[2 * k + 1])
		return

	def apply_node_lazy(self, k, op):
		self.node[k] = self.oper(op, self.node[k])
		if k < self.n:
			self.lazy[k] = self.comp(op, self.lazy[k])
		return

	def push(self, k):
		self.apply_node_lazy(2 * k, self.lazy[k])
		self.apply_node_lazy(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.idem
		return

	def set(self, k, x):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)

		self.node[k] = x
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	def get(self, k):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		return self.node[k]

	#[l, r)
	def prod(self, l, r):
		if l == r:
			return self.unit
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i) != l:
				self.push(l >> i)
			if ((r >> i) << r) != r:
				self.push(r >> i)

		s_l, s_r = self.unit, self.unit
		while l < r:
			if l & 1:
				s_l = self.func(s_l, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				s_r = self.func(self.node[r], s_r)
			l >>= 1
			r >>= 1
		return self.func(s_l, s_r)

	def all_prod(self):
		return self.node[1]

	def point_apply(self, k, op):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		self.node[k] = self.oper(op, self.node[k])
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	#operate to [l, r)
	def apply(self, l, r, op):
		if l == r:
			return
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i != l):
				self.push(l >> i)
			if ((r >> i) << i != r):
				self.push((r - 1) >> i)

		l_pres, r_pres = l, r
		while l < r:
			if l & 1:
				self.apply_node_lazy(l, op)
				l += 1
			if r & 1:
				r -= 1
				self.apply_node_lazy(r, op)
			l >>= 1
			r >>= 1
		l, r = l_pres, r_pres

		for i in range(1, self.hght+1):
			if ((l >> i) << i != l):
				self.update(l >> i)
			if ((r >> i) << i != r):
				self.update((r - 1) >> i)
		return

	#maximum of r (within [l, n)) which satisfies val(prod(l, r))
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		l += self.n
		for i in range(self.hght, 0, -1):
			self.push(l >> i)

		s = self.unit
		while True:
			while l % 2 == 0:
				l >>= 1
			if not val(self.func(s, self.node[l])):
				while l < self.n:
					self.push(l) #before descending
					l <<= 1
					if val(self.func(s, self.node[l])):
						s = self.func(s, self.node[l])
						l += 1
				return l - self.n
			s = self.func(s, self.node[l])
			l += 1
			if (l & -l) == l:
				return self.size

	#minimum of l (within [0, r)) which satisfies val(prod(l, r))
	def min_left(self, r, val):
		if r == 0:
			return 0
		r += self.n
		for i in range(self.hght, 0, -1):
			self.push((r - 1) >> i)

		s = self.unit
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not val(self.func(self.node[r], s)):
				while r < self.n:
					self.push(r) #before descending
					r = (r << 1) + 1
					if val(self.func(self.node[r], s)):
						s = self.func(self.node[r], s)
						r -= 1
				return r + 1 - self.n
			s = self.func(self.node[r], s)
			if (r & -r) == r:
				return 0

"""
node: (value, size)
lazy: value
"""
def func(x, y):
	return (min(x[0], y[0]), x[1] + y[1])

unit = (2 * (10 ** 10), 1)

def oper(value, x):
	return (x[0] + value * x[1], x[1])

def comp(f1, f2):
	return f1 + f2

idem = 0

n = int(input())
a = list(map(int, input().split()))
st = LazySegTree([(x, 1) for x in a], func, unit, oper, comp, idem)
ans = []
for _ in range(int(input())):
	k, l, r, c = map(int, input().split())
	if k == 1:
		st.apply(l-1, r, c)
	else:
		ans.append(st.prod(l-1, r)[0])
print(*ans, sep="\n")
0