- 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
- 77 lines of Python from the credited upstream file abc378_e.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- 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 26 index += index & -index27 28 def range_sum(self, left: int, right: int) -> Any:29 assert 0 <= left <= right <= self.size30 31 return self.sum(right - 1) - self.sum(left - 1)32 33 def sum(self, index: int) -> Any:34 index += 135 summed = 036 37 assert 0 <= index <= self.size38 39 while index > 0:40 summed += self.tree[index]41 index -= index & -index42 43 44 return summed45 46 47def main():48 import sys49 from itertools import accumulate50 51 input = sys.stdin.readline52 53 n, m = map(int, input().split())54 a = list(map(int, input().split()))55 s = [0]56 57 for ai in a:58 si = s[-1] + ai59 si %= m60 s += [si]61 62 acc_s = list(accumulate(s))63 bit = BIT(m)64 ans = 065 66 67 68 for right in range(1, n + 1):69 ans += s[right] * right - acc_s[right - 1] + m * bit.range_sum(s[right] + 1, m)70 bit.add(s[right], 1)71 72 print(ans)73 74 75if __name__ == "__main__":76 main()77