Submit Info #53144

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum pypy3 Eki1009 AC 9033 ms 141.11 MiB

ケース詳細
Name Status Time Memory
example_00 AC 50 ms 29.81 MiB
max_random_00 AC 8780 ms 141.11 MiB
max_random_01 AC 9033 ms 140.96 MiB
max_random_02 AC 8762 ms 140.90 MiB
medium_00 AC 372 ms 39.43 MiB
medium_01 AC 288 ms 36.56 MiB
medium_02 AC 256 ms 36.30 MiB
random2_00 AC 5337 ms 133.40 MiB
random2_01 AC 5192 ms 132.88 MiB
random2_02 AC 5277 ms 133.62 MiB
random3_00 AC 4067 ms 129.12 MiB
random3_01 AC 5593 ms 132.98 MiB
random3_02 AC 5716 ms 132.86 MiB
random_00 AC 3869 ms 105.00 MiB
random_01 AC 7485 ms 139.13 MiB
random_02 AC 5993 ms 134.30 MiB
small_00 AC 52 ms 29.81 MiB
small_01 AC 54 ms 29.79 MiB
small_02 AC 55 ms 29.88 MiB
small_03 AC 56 ms 29.80 MiB
small_04 AC 52 ms 29.89 MiB
small_05 AC 54 ms 29.88 MiB
small_06 AC 57 ms 29.80 MiB
small_07 AC 54 ms 29.80 MiB
small_08 AC 53 ms 29.88 MiB
small_09 AC 54 ms 29.85 MiB

class AngelBeats: def __init__(self, size_or_data): self.inf = 10**18 self.stack = [] if isinstance(size_or_data, int): self.n = n self.log = (self.n - 1).bit_length() self.size = 1 << self.log self.data_max_1st = [0] * (2 * self.size) self.data_max_2nd = [-self.inf] * (2 * self.size) self.data_min_1st = [0] * (2 * self.size) self.data_min_2nd = [self.inf] * (2 * self.size) self.data_max_count = [1] * (2 * self.size) self.data_min_count = [1] * (2 * self.size) self.data_sum = [0] * (2 * self.size) self.lazy_add = [0] * (2 * self.size) else: self.n = len(size_or_data) self.log = (self.n - 1).bit_length() self.size = 1 << self.log self.data_max_1st = [0] * (2 * self.size) self.data_max_2nd = [-self.inf] * (2 * self.size) self.data_min_1st = [0] * (2 * self.size) self.data_min_2nd = [self.inf] * (2 * self.size) self.data_max_count = [1] * (2 * self.size) self.data_min_count = [1] * (2 * self.size) self.data_sum = [0] * (2 * self.size) self.lazy_add = [0] * (2 * self.size) for i, a in enumerate(size_or_data, self.size): self.data_max_1st[i] = a self.data_min_1st[i] = a self.data_sum[i] = a for i in range(1, self.size)[::-1]: self.update(i) def update(self, k): self.data_sum[k] = self.data_sum[2 * k] + self.data_sum[2 * k + 1] if self.data_max_1st[2 * k] == self.data_max_1st[2 * k + 1]: self.data_max_1st[k] = self.data_max_1st[2 * k] self.data_max_2nd[k] = max(self.data_max_2nd[2 * k], self.data_max_2nd[2 * k + 1]) self.data_max_count[k] = self.data_max_count[2 * k] + self.data_max_count[2 * k + 1] else: f = int(self.data_max_1st[2 * k] < self.data_max_1st[2 * k + 1]) self.data_max_1st[k] = self.data_max_1st[2 * k + f] self.data_max_count[k] = self.data_max_count[2 * k + f] self.data_max_2nd[k] = max(self.data_max_1st[2 * k + 1 - f], self.data_max_2nd[2 * k + f]) if self.data_min_1st[2 * k] == self.data_min_1st[2 * k + 1]: self.data_min_1st[k] = self.data_min_1st[2 * k] self.data_min_2nd[k] = min(self.data_min_2nd[2 * k], self.data_min_2nd[2 * k + 1]) self.data_min_count[k] = self.data_min_count[2 * k] + self.data_min_count[2 * k + 1] else: f = int(self.data_min_1st[2 * k] > self.data_min_1st[2 * k + 1]) self.data_min_1st[k] = self.data_min_1st[2 * k + f] self.data_min_count[k] = self.data_min_count[2 * k + f] self.data_min_2nd[k] = min(self.data_min_1st[2 * k + 1 - f], self.data_min_2nd[2 * k + f]) def push_add(self, k, x): self.data_sum[k] += x << (self.log + 1 - k.bit_length()) self.data_max_1st[k] += x self.data_min_1st[k] += x if self.data_max_2nd[k] != -self.inf: self.data_max_2nd[k] += x if self.data_min_2nd[k] != self.inf: self.data_min_2nd[k] += x self.lazy_add[k] += x def push_min(self, k, x): self.data_sum[k] += (x - self.data_max_1st[k]) * self.data_max_count[k] if self.data_min_1st[k] == self.data_max_1st[k]: self.data_min_1st[k] = x if self.data_min_2nd[k] == self.data_max_1st[k]: self.data_min_2nd[k] = x self.data_max_1st[k] = x def push_max(self, k, x): self.data_sum[k] += (x - self.data_min_1st[k]) * self.data_min_count[k] if self.data_max_1st[k] == self.data_min_1st[k]: self.data_max_1st[k] = x if self.data_max_2nd[k] == self.data_min_1st[k]: self.data_max_2nd[k] = x self.data_min_1st[k] = x def push(self, k): if self.lazy_add[k]: self.push_add(2 * k, self.lazy_add[k]) self.push_add(2 * k + 1, self.lazy_add[k]) self.lazy_add[k] = 0 if self.data_max_1st[k] < self.data_max_1st[2 * k]: self.push_min(2 * k, self.data_max_1st[k]) if self.data_min_1st[k] > self.data_min_1st[2 * k]: self.push_max(2 * k, self.data_min_1st[k]) if self.data_max_1st[k] < self.data_max_1st[2 * k + 1]: self.push_min(2 * k + 1, self.data_max_1st[k]) if self.data_min_1st[k] > self.data_min_1st[2 * k + 1]: self.push_max(2 * k + 1, self.data_min_1st[k]) def subtree_chmin(self, k, x): self.stack = [k] while self.stack: k = self.stack.pop() if k >= 0: if self.data_max_1st[k] <= x: continue if self.data_max_2nd[k] < x: self.push_min(k, x) continue self.push(k) self.stack.append(~k) self.stack.append(2 * k) self.stack.append(2 * k + 1) else: k = ~k self.update(k) def subtree_chmax(self, k, x): self.stack = [k] while self.stack: k = self.stack.pop() if k >= 0: if self.data_min_1st[k] >= x: continue if self.data_min_2nd[k] > x: self.push_max(k, x) continue self.push(k) self.stack.append(~k) self.stack.append(2 * k) self.stack.append(2 * k + 1) else: k = ~k self.update(k) def range_chmin(self, l, r, x): if l == r: return l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) l2 = l r2 = r while l < r: if l & 1: self.subtree_chmin(l, x) l += 1 if r & 1: r -= 1 self.subtree_chmin(r, x) l >>= 1 r >>= 1 l = l2 r = r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self.update(l >> i) if ((r >> i) << i) != r: self.update((r - 1) >> i) def range_chmax(self, l, r, x): if l == r: return l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) l2 = l r2 = r while l < r: if l & 1: self.subtree_chmax(l, x) l += 1 if r & 1: r -= 1 self.subtree_chmax(r, x) l >>= 1 r >>= 1 l = l2 r = r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self.update(l >> i) if ((r >> i) << i) != r: self.update((r - 1) >> i) def range_add(self, l, r, x): if l == r: return l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) l2 = l r2 = r while l < r: if l & 1: self.push_add(l, x) l += 1 if r & 1: r -= 1 self.push_add(r, x) l >>= 1 r >>= 1 l = l2 r = r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self.update(l >> i) if ((r >> i) << i) != r: self.update((r - 1) >> i) def range_set(self, l, r, x): if l == r: return l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) l2 = l r2 = r while l < r: if l & 1: self.subtree_chmin(l, x) self.subtree_chmax(l, x) l += 1 if r & 1: r -= 1 self.subtree_chmin(r, x) self.subtree_chmax(r, x) l >>= 1 r >>= 1 l = l2 r = r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self.update(l >> i) if ((r >> i) << i) != r: self.update((r - 1) >> i) def prod_min(self, l, r): if l == r: return self.inf l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) res = self.inf while l < r: if l & 1: res = min(res, self.data_min_1st[l]) l += 1 if r & 1: r -= 1 res = min(res, self.data_min_1st[r]) l >>= 1 r >>= 1 return res def prod_max(self, l, r): if l == r: return -self.inf l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) res = -self.inf while l < r: if l & 1: res = max(res, self.data_max_1st[l]) l += 1 if r & 1: r -= 1 res = max(res, self.data_max_1st[r]) l >>= 1 r >>= 1 return res def prod_sum(self, l, r): if l == r: return 0 l += self.size r += self.size for i in range(1, self.log + 1)[::-1]: if ((l >> i) << i) != l: self.push(l >> i) if ((r >> i) << i) != r: self.push((r - 1) >> i) res = 0 while l < r: if l & 1: res += self.data_sum[l] l += 1 if r & 1: r -= 1 res += self.data_sum[r] l >>= 1 r >>= 1 return res import sys input = sys.stdin.readline n, q = map(int, input().split()) A = tuple(map(int, input().split())) ab = AngelBeats(A) ANS = [] for _ in range(q): t, *P = map(int, input().split()) if t == 0: l, r, b = P ab.range_chmin(l, r, b) elif t == 1: l, r, b = P ab.range_chmax(l, r, b) elif t == 2: l, r, b = P ab.range_add(l, r, b) else: l, r = P ANS.append(ab.prod_sum(l, r)) print('\n'.join(map(str, ANS)))