- 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
- 112 lines of Python from the credited upstream file abc396_f.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 3 4from typing import Any5 6 7class BIT:8 """Binary Indexed Tree (Fenwick Tree)9 10 See:11 https:atcoder.jp/contests/tessoku-book/submissions/3491243412 """13 14 def __init__(self, size: int) -> None:15 self.size = size16 self.size0 = 1 << (size.bit_length() - 1)17 self.tree = [0] * (size + 1)18 19 def add(self, index: int, value: Any) -> None:20 assert 0 <= index < self.size21 22 index += 123 24 while index <= self.size:25 self.tree[index] += value26 27 index += index & -index28 29 def get(self, index: int) -> Any:30 return self.sum(index) - self.sum(index - 1)31 32 def range_sum(self, left: int, right: int) -> Any:33 assert 0 <= left <= right <= self.size34 35 return self.sum(right - 1) - self.sum(left - 1)36 37 def sum(self, index: int) -> Any:38 index += 139 summed = 040 41 assert 0 <= index <= self.size42 43 while index > 0:44 summed += self.tree[index]45 index -= index & -index46 47 48 return summed49 50 def lower_bound(self, value: Any) -> int:51 pos = 052 plus = self.size053 54 while plus > 0:55 if pos + plus <= self.size and self.tree[pos + plus] < value:56 value -= self.tree[pos + plus]57 pos += plus58 59 plus = 260 61 return pos62 63 646566def calc_inversion_number(array: list[int]) -> int:67 compressed_dict = {68 element: index for index, element in enumerate(sorted(set(array)))69 }70 compressed_list = [compressed_dict[ai] for ai in array]71 72 size = len(compressed_list)73 bit = BIT(size)74 inversion_number = 075 76 for index, value in enumerate(compressed_list):77 inversion_number += index - bit.sum(value)78 bit.add(value, 1)79 80 return inversion_number81 82 83def main():84 import sys85 86 input = sys.stdin.readline87 88 n, m = map(int, input().split())89 a = list(map(int, input().split()))90 c = list()91 92 for i, ai in enumerate(a):93 c.append((ai, i))94 95 c.sort()96 count = calc_inversion_number(a)97 ans = list()98 99 for x in range(m - 1, -1, -1):100 ans.append(count)101 102 while c and c[-1][0] == x:103 _, j = c.pop()104 count += j105 count -= n - 1 - j106 107 print(*ans, sep="\n")108 109 110if __name__ == "__main__":111 main()112