- 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
- 75 lines of Python from the credited upstream file abc441_e.py.
- The implementation keeps its working state in language-native values and containers.
- 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 3from typing import Any4 5 6class BIT:7 """Binary Indexed Tree (Fenwick Tree)8 9 See:10 https:atcoder.jp/contests/tessoku-book/submissions/3491243411 """12 13 def __init__(self, size: int) -> None:14 self.size = size15 self.size0 = 1 << (size.bit_length() - 1)16 self.tree = [0] * (size + 1)17 18 def add(self, index: int, value: Any) -> None:19 assert 0 <= index < self.size20 21 index += 122 23 while index <= self.size:24 self.tree[index] += value25 index += index & -index26 27 def range_sum(self, left: int, right: int) -> Any:28 assert 0 <= left <= right <= self.size29 30 return self.sum(right - 1) - self.sum(left - 1)31 32 def sum(self, index: int) -> Any:33 index += 134 summed = 035 36 assert 0 <= index <= self.size37 38 while index > 0:39 summed += self.tree[index]40 index -= index & -index41 42 return summed43 44 45def main():46 import sys47 48 input = sys.stdin.readline49 50 n = int(input())51 s = input().rstrip()52 d = [n]53 54 for si in s:55 d.append(d[-1])56 57 if si == "A":58 d[-1] += 159 elif si == "B":60 d[-1] -= 161 62 size = 2 * n + 163 bit = BIT(size)64 ans = 065 66 for di in d:67 ans += bit.range_sum(0, di)68 bit.add(di, 1)69 70 print(ans)71 72 73if __name__ == "__main__":74 main()75