結果

問題 No.876 Range Compress Query
ユーザー anagohirameanagohirame
提出日時 2021-02-18 01:09:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 2,507 bytes
コンパイル時間 716 ms
コンパイル使用メモリ 87,360 KB
実行使用メモリ 94,828 KB
最終ジャッジ日時 2023-10-12 10:48:34
合計ジャッジ時間 4,484 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,436 KB
testcase_01 AC 88 ms
76,724 KB
testcase_02 AC 73 ms
71,284 KB
testcase_03 AC 91 ms
76,488 KB
testcase_04 AC 77 ms
75,704 KB
testcase_05 AC 77 ms
75,848 KB
testcase_06 AC 91 ms
76,384 KB
testcase_07 AC 90 ms
76,672 KB
testcase_08 AC 88 ms
76,512 KB
testcase_09 AC 88 ms
76,588 KB
testcase_10 AC 88 ms
76,736 KB
testcase_11 AC 245 ms
90,888 KB
testcase_12 AC 219 ms
89,432 KB
testcase_13 AC 221 ms
91,136 KB
testcase_14 AC 234 ms
91,176 KB
testcase_15 AC 208 ms
92,728 KB
testcase_16 AC 235 ms
94,296 KB
testcase_17 AC 239 ms
94,828 KB
testcase_18 AC 247 ms
94,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class SegTree():
	def __init__(self, a, func, unit):
		#the number of nodes is 2n-1
		self.n = 1 << len(a).bit_length()
		self.size = len(a)
		self.func = func
		self.unit = unit
		self.node = [unit] * (2*self.n-1)
		for i in range(len(a)+self.n-2, -1, -1):
			if i >= self.n-1:
				self.node[i] = a[i-self.n+1]
			else:
				self.node[i] = self.func(self.node[2*i+1], self.node[2*i+2])

	def get(self, x):
		return self.node[x+self.n-1]

	def set(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = self.func(self.node[2*x+1], self.node[2*x+2])
		return

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

	#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 = l + self.n
		s = self.unit
		while True:
			while (L % 2 == 0):
				L >>= 1
			if not val(self.func(s, self.node[L-1])):
				while L < self.n:
					L <<= 1
					if val(self.func(s, self.node[L-1])):
						s = self.func(s, self.node[L-1])
						L += 1
				return L - self.n
			s = self.func(s, self.node[L-1])
			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 = r + self.n
		s = self.unit
		while True:
			R -= 1
			while R > 1 and R % 2:
				R >>= 1
			if not val(self.func(self.node[R-1], s)):
				while R < self.n:
					R = (R << 1) + 1
					if val(self.func(self.node[R-1], s)):
						s = self.func(self.node[R-1], s)
						R -= 1
				return R + 1 - self.n
			s = self.func(self.node[R-1], s)
			if (R & -R) == R:
				return 0

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i]-a[i-1] for i in range(1, n)]
c = [1 if x else 0 for x in b]
st = SegTree(c, lambda x, y: x+y, 0)
ans = []
for _ in range(q):
	s = list(map(int, input().split()))
	if s[0] == 1:
		l, r, x = s[1]-1, s[2]-1, s[3]
		if l > 0:
			b[l-1] += x
			if b[l-1] == 0:
				st.set(l-1, 0)
			else:
				st.set(l-1, 1)
		if r < n-1:
			b[r] -= x
			if b[r] == 0:
				st.set(r, 0)
			else:
				st.set(r, 1)
	else:
		l, r = s[1]-1, s[2]-1
		ans.append(st.prod(l, r) + 1)
print(*ans, sep="\n")
0