結果
問題 | No.2992 Range ABCD String Query |
ユーザー |
|
提出日時 | 2024-12-16 22:17:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,390 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,976 KB |
実行使用メモリ | 377,348 KB |
最終ジャッジ日時 | 2024-12-16 23:55:58 |
合計ジャッジ時間 | 140,791 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 TLE * 8 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import defaultdictimport typingdef _ceil_pow2(n: int) -> int:x = 0while (1 << x) < n:x += 1return xdef _bsf(n: int) -> int:x = 0while n % 2 == 0:x += 1n //= 2return xclass SegTree:def __init__(self,op: typing.Callable[[typing.Any, typing.Any], typing.Any],e: typing.Any,v: typing.Union[int, typing.List[typing.Any]]) -> None:self._op = opself._e = eif isinstance(v, int):v = [e] * vself._n = len(v)self._log = _ceil_pow2(self._n)self._size = 1 << self._logself._d = [e] * (2 * self._size)for i in range(self._n):self._d[self._size + i] = v[i]for i in range(self._size - 1, 0, -1):self._update(i)def set(self, p: int, x: typing.Any) -> None:assert 0 <= p < self._np += self._sizeself._d[p] = xfor i in range(1, self._log + 1):self._update(p >> i)def get(self, p: int) -> typing.Any:assert 0 <= p < self._nreturn self._d[p + self._size]def prod(self, left: int, right: int) -> typing.Any:assert 0 <= left <= right <= self._nsml = self._esmr = self._eleft += self._sizeright += self._sizewhile left < right:if left & 1:sml = self._op(sml, self._d[left])left += 1if right & 1:right -= 1smr = self._op(self._d[right], smr)left >>= 1right >>= 1return self._op(sml, smr)def all_prod(self) -> typing.Any:return self._d[1]def max_right(self, left: int,f: typing.Callable[[typing.Any], bool]) -> int:assert 0 <= left <= self._nassert f(self._e)if left == self._n:return self._nleft += self._sizesm = self._efirst = Truewhile first or (left & -left) != left:first = Falsewhile left % 2 == 0:left >>= 1if not f(self._op(sm, self._d[left])):while left < self._size:left *= 2if f(self._op(sm, self._d[left])):sm = self._op(sm, self._d[left])left += 1return left - self._sizesm = self._op(sm, self._d[left])left += 1return self._ndef min_left(self, right: int,f: typing.Callable[[typing.Any], bool]) -> int:assert 0 <= right <= self._nassert f(self._e)if right == 0:return 0right += self._sizesm = self._efirst = Truewhile first or (right & -right) != right:first = Falseright -= 1while right > 1 and right % 2:right >>= 1if not f(self._op(self._d[right], sm)):while right < self._size:right = 2 * right + 1if f(self._op(self._d[right], sm)):sm = self._op(self._d[right], sm)right -= 1return right + 1 - self._sizesm = self._op(self._d[right], sm)return 0def _update(self, k: int) -> None:self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])def op(l, r):return (l[0] + r[0], min(l[0] + r[1], l[1] + r[4]), min(l[0] + r[2], l[1] + r[5], l[2] + r[7]), min(l[0] + r[3], l[1] + r[6], l[2] + r[8], l[3] +r[9]), l[4] + r[4], min(l[4] + r[5], l[5] + r[7]), min(l[4] + r[6], l[5] + r[8], l[6] + r[9]), l[7] + r[7], min(l[7] + r[8], l[8] + r[9]),l[9] + r[9])e = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)d = defaultdict(tuple)d['A'] = (0, 0, 0, 0, 1, 1, 1, 1, 1, 1)d['B'] = (1, 0, 0, 0, 0, 0, 0, 1, 1, 1)d['C'] = (1, 1, 0, 0, 1, 0, 0, 0, 0, 1)d['D'] = (1, 1, 1, 0, 1, 1, 0, 1, 0, 0)N, Q = map(int, input().split())S = input()v = [d[S[i]] for i in range(N)]seg = SegTree(op, e, v)for _ in range(Q):t, a, b = input().split()if t == '1':a = int(a) - 1seg.set(a, d[b[0]])else:a = int(a) - 1b = int(b) - 1print(seg.prod(a, b + 1)[3])