結果
問題 | No.2992 Range ABCD String Query |
ユーザー |
👑 |
提出日時 | 2024-12-17 00:21:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 5,848 ms / 6,000 ms |
コード長 | 4,047 bytes |
コンパイル時間 | 420 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 298,044 KB |
最終ジャッジ日時 | 2024-12-17 00:24:01 |
合計ジャッジ時間 | 155,212 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
class SegmentTreeBase_:def ope(self, l, r):raise NotImplementedErrordef e(self):raise NotImplementedErrordef __init__(self, n, init=None):self.n = nself.n0 = 1 << (n - 1).bit_length()self.data = [self.e()] * (2 * self.n0)if init is not None:for i in range(n):self.data[self.n0 + i] = init[i]for i in range(self.n0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def build(self):for i in range(self.n0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def set(self, i, x):i += self.n0self.data[i] = xwhile i > 1:i >>= 1self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def get(self, i):return self.data[i + self.n0]def __getitem__(self, i):return self.data[i + self.n0]def __setitem__(self, i, x):self.set(i, x)def prod(self, l, r):assert 0 <= l <= r <= self.n0l += self.n0r += self.n0lles = self.e()rres = self.e()while l < r:if l & 1:lles = self.ope(lles, self.data[l])l += 1if r & 1:r -= 1rres = self.ope(self.data[r], rres)l >>= 1r >>= 1return self.ope(lles, rres)def max_right(self, l, f):if l == self.n:return self.nl += self.n0sm = self.e()while 1:while l % 2 == 0:l >>= 1if not f(self.ope(sm, self.data[l])):while l < self.n0:l <<= 1if f(self.ope(sm, self.data[l])):sm = self.ope(sm, self.data[l])l += 1return l - self.n0sm = self.ope(sm, self.data[l])l += 1if l & -l == l:breakreturn self.ndef min_left(self, r, f):if r == 0:return 0r += self.n0sm = self.e()while 1:r -= 1while r > 1 and r % 2:r >>= 1if not f(self.ope(self.data[r], sm)):while r < self.n0:r = 2 * r + 1if f(self.ope(self.data[r], sm)):sm = self.ope(self.data[r], sm)r -= 1return r + 1 - self.n0sm = self.ope(self.data[r], sm)if r & -r == r:breakreturn 0class segtree(SegmentTreeBase_):def ope(self, l, r):ret = [0] * 16for i in range(4):for j in range(i, 4):for k in range(i, j + 1):ret[i * 4 + j] = max(ret[i * 4 + j], l[i * 4 + k] + r[k * 4 + j])return retdef e(self):return [0] * 16n, Q = map(int, input().split())S = input()a = [0] * 16b = [0] * 16c = [0] * 16d = [0] * 16for i in range(4):for j in range(i, 4):if i <= 0 <= j:a[i * 4 + j] = 1if i <= 1 <= j:b[i * 4 + j] = 1if i <= 2 <= j:c[i * 4 + j] = 1if i <= 3 <= j:d[i * 4 + j] = 1data = [None] * nfor i, s in enumerate(S):if s == "A":data[i] = a[:]elif s == "B":data[i] = b[:]elif s == "C":data[i] = c[:]else:data[i] = d[:]seg = segtree(n, data)for _ in range(Q):query = input().split()if query[0] == "1":x, s = int(query[1]) - 1, query[2]if s == "A":seg.set(x, a[:])elif s == "B":seg.set(x, b[:])elif s == "C":seg.set(x, c[:])else:seg.set(x, d[:])else:l, r = map(int, query[1:])print(r - l + 1 - seg.prod(l - 1, r)[3])