結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2021-05-11 06:25:12 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,245 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 281,788 KB |
最終ジャッジ日時 | 2024-09-21 12:08:08 |
合計ジャッジ時間 | 21,200 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 TLE * 5 |
ソースコード
class LazySegmentTree:#seg = LazySegmentTree(op_X, e_X, mapping, composision_of_Aut_X, id_of_Aut_X, N, array=None)def __init__(self, op_X, e_X, mapping, composision_of_Aut_X, id_of_Aut_X, N, array=None):# それぞれ Xの演算, 単位元, f(x), f\circ g, Xの恒等変換# M が X に作用する#__slots__ = ["op_X", "e_X", "mapping","compose","id_M","N","log","N0","data","lazy"]self.e_X = e_X; self.op_X = op_X; self.mapping = mapping; self.compose = composision_of_Aut_X; self.id_M = id_of_Aut_Xself.N = Nself.log = (N-1).bit_length()self.N0 = 1<<self.logself.data = [e_X]*(2*self.N0)self.lazy = [self.id_M]*self.N0if array is not None:assert N == len(array)self.data[self.N0:self.N0+self.N] = arrayfor i in range(self.N0-1,0,-1): self.update(i)# 1点更新def point_set(self, p, x):p += self.N0for i in range(self.log, 0,-1):self.push(p>>i)self.data[p] = xfor i in range(1, self.log + 1):self.update(p>>i)# 1点取得def point_get(self, p):p += self.N0for i in range(self.log, 0, -1):self.push(p>>i)return self.data[p]# 半開区間[L,R)をopでまとめるdef prod(self, l, r):if l == r: return self.e_Xl += self.N0r += self.N0for i in range(self.log, 0, -1):if (l>>i)<<i != l:self.push(l>>i)if (r>>i)<<i != r:self.push(r>>i)sml = smr = self.e_Xwhile l < r:if l & 1:sml = self.op_X(sml, self.data[l])l += 1if r & 1:r -= 1smr = self.op_X(self.data[r], smr)l >>= 1r >>= 1return self.op_X(sml, smr)# 全体をopでまとめるdef all_prod(self): return self.data[1]# 1点作用def apply_point(self, p, f):p += self.N0for i in range(self.log, 0, -1):self.push(p>>i)self.data[p] = self.mapping(f, self.data[p])for i in range(1, self.log + 1):self.update(p>>i)# 区間作用def apply(self, l, r, f):if l == r: returnl += self.N0r += self.N0for i in range(self.log, 0, -1):if (l>>i)<<i != l:self.push(l>>i)if (r>>i)<<i != r:self.push((r-1)>>i)l2, r2 = l, rwhile l < r:if l & 1:self.all_apply(l, f)l += 1if r & 1:r -= 1self.all_apply(r, f)l >>= 1r >>= 1l, r = l2, r2for 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)"""始点 l を固定f(x_l*...*x_{r-1}) が True になる最大の rつまり TTTTFFFF となるとき、F となる最小の添え字存在しない場合 n が返るf(e_M) = True でないと壊れる"""def max_right(self, l, g):if l == self.N: return self.Nl += self.N0for i in range(self.log, 0, -1): self.push(l>>i)sm = self.e_Xwhile True:while l&1 == 0:l >>= 1if not g(self.op_X(sm, self.data[l])):while l < self.N0:self.push(l)l *= 2if g(self.op_X(sm, self.data[l])):sm = self.op_X(sm, self.data[l])l += 1return l - self.N0sm = self.op_X(sm, self.data[l])l += 1if l&-l == l: breakreturn self.N"""終点 r を固定f(x_l*...*x_{r-1}) が True になる最小の lつまり FFFFTTTT となるとき、T となる最小の添え字存在しない場合 r が返るf(e_M) = True でないと壊れる"""def min_left(self, r, g):if r == 0: return 0r += self.N0for i in range(self.log, 0, -1): self.push((r-1)>>i)sm = self.e_Xwhile True:r -= 1while r>1 and r&1:r >>= 1if not g(self.op_X(self.data[r], sm)):while r < self.N0:self.push(r)r = 2*r + 1if g(self.op_X(self.data[r], sm)):sm = self.op_X(self.data[r], sm)r -= 1return r + 1 - self.N0sm = self.op_X(self.data[r], sm)if r&-r == r: breakreturn 0# 以下内部関数def update(self, k):self.data[k] = self.op_X(self.data[2*k], self.data[2*k+1])def all_apply(self, k, f):self.data[k] = self.mapping(f, self.data[k])if k < self.N0:self.lazy[k] = self.compose(f, self.lazy[k])def push(self, k): #propagate と同じif self.lazy[k] is self.id_M: returnself.data[2*k ] = self.mapping(self.lazy[k], self.data[2*k])self.data[2*k+1] = self.mapping(self.lazy[k], self.data[2*k+1])if 2*k < self.N0:self.lazy[2*k] = self.compose(self.lazy[k], self.lazy[2*k])self.lazy[2*k+1] = self.compose(self.lazy[k], self.lazy[2*k+1])self.lazy[k] = self.id_Mdef op_X(X,Y):return(X[0]+Y[0],X[1]+Y[1],X[2]+Y[2])e_X = (0,0,0)def mapping(v,X):a,b,d = Xreturn (a+v*d, b+v*(2*a+v*d), d)def composision_of_Aut_X(v,w):return v+wid_of_Aut_X = 0import sysreadline = sys.stdin.readlinen = int(readline())*a, = map(int,readline().split())array = [(ai,ai*ai,1) for ai in a]seg = LazySegmentTree(op_X, e_X, mapping, composision_of_Aut_X, id_of_Aut_X, n, array)Q = int(readline())for _ in range(Q):v,*q = map(int,readline().split())if v==1:l,r,x = qseg.apply(l-1,r,x)else:l,r = qprint(seg.prod(l-1,r)[1])