- Choose the aggregate stored for each interval or prefix.
- Build or initialize the structure from the input.
- Apply updates and combine the affected nodes to answer each query.
Code notes
- 82 lines of Python from the credited upstream file abc157_e.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Count the build once, then multiply the logarithmic update or query path by the number of operations.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4class BIT:5 """Binary Indexed Tree (Fenwick Tree)6 Args:7 size: List size (greater than 0).8 """9 10 def __init__(self, size: int):11 self.size = size12 self._bit = [0 for _ in range(self.size + 1)]13 14 def add(self, index: int, value: int) -> None:15 """Adds value to list with index i.16 Args:17 index: The number of index (1-indexed).18 value: A value19 Landau notation: O(log n)20 """21 22 while index <= self.size:23 self._bit[index] += value24 index += index & -index25 26 def sum(self, index) -> int:27 """Calculate the sum of elements from 1 to index.28 Args:29 index: The number of index (1-indexed).30 Returns:31 The sum of elements from 1 to index.32 Landau notation: O(log n)33 """34 35 summed = 036 37 while index > 0:38 summed += self._bit[index]39 index -= index & -index40 41 return summed42 43 44def main():45 import sys46 47 input = sys.stdin.readline48 49 n = int(input())50 s = list(input().rstrip())51 q = int(input())52 bits = [BIT(n) for _ in range(26)]53 54 for index, si in enumerate(s, 1):55 c = ord(si) - ord("a")56 bits[c].add(index, 1)57 58 for i in range(q):59 query = list(input().split())60 61 if query[0] == "1":62 iq = int(query[1])63 cq = ord(query[2]) - ord("a")64 si = ord(s[iq - 1]) - ord("a")65 66 bits[si].add(iq, -1)67 s[iq - 1] = query[2]68 bits[cq].add(iq, 1)69 else:70 lq, rq = int(query[1]), int(query[2])71 ans = 072 73 for bit in bits:74 if bit.sum(rq) - bit.sum(lq - 1) > 0:75 ans += 176 77 print(ans)78 79 80if __name__ == "__main__":81 main()82