結果
問題 | No.2554 MMA文字列2 (Query Version) |
ユーザー | StanMarsh |
提出日時 | 2023-11-30 16:48:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,119 ms / 5,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 735 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 271,912 KB |
最終ジャッジ日時 | 2023-11-30 16:50:19 |
合計ジャッジ時間 | 109,348 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
61,744 KB |
testcase_01 | AC | 46 ms
61,744 KB |
testcase_02 | AC | 104 ms
77,160 KB |
testcase_03 | AC | 109 ms
76,940 KB |
testcase_04 | AC | 138 ms
79,000 KB |
testcase_05 | AC | 115 ms
78,104 KB |
testcase_06 | AC | 113 ms
77,832 KB |
testcase_07 | AC | 110 ms
76,648 KB |
testcase_08 | AC | 85 ms
77,456 KB |
testcase_09 | AC | 132 ms
78,872 KB |
testcase_10 | AC | 122 ms
79,128 KB |
testcase_11 | AC | 95 ms
76,424 KB |
testcase_12 | AC | 395 ms
107,920 KB |
testcase_13 | AC | 2,483 ms
268,744 KB |
testcase_14 | AC | 738 ms
123,204 KB |
testcase_15 | AC | 2,113 ms
263,044 KB |
testcase_16 | AC | 1,571 ms
183,416 KB |
testcase_17 | AC | 2,051 ms
236,896 KB |
testcase_18 | AC | 895 ms
120,872 KB |
testcase_19 | AC | 1,137 ms
157,840 KB |
testcase_20 | AC | 2,426 ms
269,364 KB |
testcase_21 | AC | 1,111 ms
138,024 KB |
testcase_22 | AC | 2,819 ms
269,328 KB |
testcase_23 | AC | 2,797 ms
268,856 KB |
testcase_24 | AC | 2,933 ms
269,240 KB |
testcase_25 | AC | 2,858 ms
268,760 KB |
testcase_26 | AC | 2,868 ms
268,856 KB |
testcase_27 | AC | 2,827 ms
268,984 KB |
testcase_28 | AC | 2,947 ms
269,496 KB |
testcase_29 | AC | 2,871 ms
269,112 KB |
testcase_30 | AC | 2,884 ms
268,660 KB |
testcase_31 | AC | 2,708 ms
269,112 KB |
testcase_32 | AC | 458 ms
79,272 KB |
testcase_33 | AC | 457 ms
79,644 KB |
testcase_34 | AC | 443 ms
79,300 KB |
testcase_35 | AC | 504 ms
80,552 KB |
testcase_36 | AC | 493 ms
80,940 KB |
testcase_37 | AC | 2,537 ms
201,400 KB |
testcase_38 | AC | 2,550 ms
200,316 KB |
testcase_39 | AC | 2,520 ms
200,848 KB |
testcase_40 | AC | 2,590 ms
202,392 KB |
testcase_41 | AC | 2,682 ms
202,820 KB |
testcase_42 | AC | 2,724 ms
227,968 KB |
testcase_43 | AC | 2,766 ms
227,052 KB |
testcase_44 | AC | 2,720 ms
227,896 KB |
testcase_45 | AC | 2,653 ms
227,512 KB |
testcase_46 | AC | 2,625 ms
227,768 KB |
testcase_47 | AC | 2,945 ms
270,756 KB |
testcase_48 | AC | 2,910 ms
270,792 KB |
testcase_49 | AC | 2,895 ms
271,172 KB |
testcase_50 | AC | 2,946 ms
270,392 KB |
testcase_51 | AC | 2,842 ms
270,264 KB |
testcase_52 | AC | 2,928 ms
271,912 KB |
testcase_53 | AC | 3,028 ms
271,860 KB |
testcase_54 | AC | 3,119 ms
270,568 KB |
testcase_55 | AC | 2,990 ms
271,876 KB |
testcase_56 | AC | 2,983 ms
271,548 KB |
ソースコード
class segt: def __init__(self, n, calc): self.num = 2 ** (n - 1).bit_length() self.data = [[0] * 53 for _ in range(2 * self.num)] self.calc = calc def update(self, idx, x): idx += self.num - 1 self.data[idx] = [0] * 53 self.data[idx][x] = 1 while idx > 0: idx = (idx - 1) >> 1 self.data[idx] = self.calc( self.data[2 * idx + 1][:], self.data[2 * idx + 2][:] )[:] def renew(self, idx, x): self.update(idx, self.calc(self.get(idx), x)) def prod(self, left, right): l = left + self.num r = right + self.num res_l = [0] * 53 res_r = [0] * 53 while l < r: if l % 2: res_l = self.calc(res_l[:], self.data[l - 1][:])[:] l += 1 if r % 2: r -= 1 res_r = self.calc(self.data[r - 1][:], res_r[:])[:] l >>= 1 r >>= 1 return self.calc(res_l, res_r) def get(self, idx): return self.data[idx + self.num - 1] def func(x, y): res = [x[i] + y[i] for i in range(53)] s = sum(y[:26]) for i in range(26): res[i + 26] += x[i] * (s - y[i]) for i in range(26): res[52] += x[i] * (x[i] - 1) // 2 * (s - y[i]) res[52] += x[i] * y[i + 26] return res n = int(input()) s = list(map(lambda x: ord(x) - 65, input())) st = segt(n, func) for i in range(n): st.update(i, s[i]) for _ in range(int(input())): t, x, y = map(str, input().split()) if t == "1": x = int(x) - 1 y = ord(y) - 65 st.update(x, y) else: l = int(x) - 1 r = int(y) print(st.prod(l, r)[52])