結果

問題 No.876 Range Compress Query
ユーザー anagohirameanagohirame
提出日時 2021-02-18 00:54:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,532 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 93,968 KB
最終ジャッジ日時 2024-09-14 09:25:09
合計ジャッジ時間 4,702 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,124 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

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 a[i] == a[i-1] else 0 for i in range(1, n)]
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) + 1)
print(*ans, sep="\n")
0