結果
問題 | No.879 Range Mod 2 Query |
ユーザー | maspy |
提出日時 | 2020-04-30 19:08:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,722 ms / 3,000 ms |
コード長 | 3,650 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 87,076 KB |
実行使用メモリ | 221,548 KB |
最終ジャッジ日時 | 2023-08-22 12:44:52 |
合計ジャッジ時間 | 28,422 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,164 KB |
testcase_01 | AC | 172 ms
77,912 KB |
testcase_02 | AC | 216 ms
79,252 KB |
testcase_03 | AC | 198 ms
79,160 KB |
testcase_04 | AC | 225 ms
80,468 KB |
testcase_05 | AC | 146 ms
77,788 KB |
testcase_06 | AC | 104 ms
76,980 KB |
testcase_07 | AC | 213 ms
79,704 KB |
testcase_08 | AC | 214 ms
80,388 KB |
testcase_09 | AC | 134 ms
77,436 KB |
testcase_10 | AC | 184 ms
78,372 KB |
testcase_11 | AC | 2,536 ms
210,256 KB |
testcase_12 | AC | 2,084 ms
165,196 KB |
testcase_13 | AC | 2,111 ms
185,380 KB |
testcase_14 | AC | 1,984 ms
184,860 KB |
testcase_15 | AC | 2,009 ms
175,448 KB |
testcase_16 | AC | 2,514 ms
214,584 KB |
testcase_17 | AC | 2,722 ms
219,764 KB |
testcase_18 | AC | 2,631 ms
221,548 KB |
testcase_19 | AC | 1,499 ms
189,248 KB |
testcase_20 | AC | 1,436 ms
186,996 KB |
testcase_21 | AC | 1,521 ms
193,688 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines class LazySegTree: def __init__(self, N, X_f, X_unit, A_f, A_unit, operate): self.N = N self.X_f = X_f self.X_unit = X_unit self.A_f = A_f self.A_unit = A_unit self.operate = operate self.X = [self.X_unit] * (N + N) self.A = [self.A_unit] * (N + N) def build(self, seq): for i, x in enumerate(seq, N): self.X[i] = x for i in range(N - 1, 0, -1): self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1]) def _eval_at(self, i): return self.operate(self.X[i], self.A[i]) def _propagate_at(self, i): if self.A[i] == self.A_unit: return self.X[i] = self._eval_at(i) self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i]) self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i]) self.A[i] = self.A_unit def _propagate_above(self, i): H = i.bit_length() - 1 for h in range(H, 0, -1): self._propagate_at(i >> h) def _recalc_above(self, i): while i > 1: i >>= 1 self.X[i] = self.X_f(self._eval_at(i << 1), self._eval_at(i << 1 | 1)) def set_val(self, i, x): i += self.N self._propagate_above(i) self.X[i] = x self.A[i] = self.A_unit self._recalc_above(i) def operate_range(self, L, R, x): L += self.N R += self.N L0 = L // (L & -L) R0 = R // (R & -R) - 1 self._propagate_above(L0) self._propagate_above(R0) while L < R: if L & 1: self.A[L] = self.A_f(self.A[L], x) L += 1 if R & 1: R -= 1 self.A[R] = self.A_f(self.A[R], x) L >>= 1 R >>= 1 self._recalc_above(L0) self._recalc_above(R0) def fold(self, L, R): L += self.N R += self.N self._propagate_above(L // (L & -L)) self._propagate_above(R // (R & -R) - 1) vL = vR = self.X_unit while L < R: if L & 1: vL = self.X_f(vL, self._eval_at(L)) L += 1 if R & 1: R -= 1 vR = self.X_f(self._eval_at(R), vR) L >>= 1 R >>= 1 return self.X_f(vL, vR) X_unit = (0, 0, 0) # even, odd, sum A_unit = (2, 0) def X_f(x, y): return (x[0] + y[0], x[1] + y[1], x[2] + y[2]) def A_f(x, y): if y[0] <= 1: return ((x[0] + x[1] + y[0]) & 1, y[1]) return (x[0], x[1] + y[1]) def operate(x, a): ev, od, su = x t, add = a if t == 2: if add & 1: return (od, ev, su + add * (ev + od)) return (ev, od, su + add * (ev + od)) if t == 1: ev, od = od, ev su = od + add * (ev + od) if add & 1: ev, od = od, ev return (ev, od, su) N, Q = map(int, readline().split()) seg = LazySegTree(N, X_f, X_unit, A_f, A_unit, operate) A = map(int, readline().split()) A = ((0, 1, x) if x & 1 else (1, 0, x) for x in A) seg.build(A) for query in readlines(): if query.startswith(b'1'): L, R = map(int, query[2:].split()) seg.operate_range(L - 1, R, (0, 0)) elif query.startswith(b'2'): L, R, x = map(int, query[2:].split()) seg.operate_range(L - 1, R, (2, x)) elif query.startswith(b'3'): L, R = map(int, query[2:].split()) ev = 0 od = 0 print(seg.fold(L - 1, R)[2])