##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Prefix sums + segment tree
core idea: range sum .
You want to count pairs where .
Rearranging: . Algorithm:
Compute all prefix sums
Coordinate compress prefix values
Iterate through prefix sums; for each, query how many previous prefix sums fall in the valid range
Add current prefix sum to segment tree You're solving a classic "count inversions" variant using segment tree. Time: . Space: .
