### omggg's blog

By omggg, 3 years ago,

Ques : Find number of inversion counts in Range [L,R] for Q queries. ****

Array Size <=1000 ; Each integer from 1 to n occurs exactly once in this array.

Queries<= 100000

What is the best method you can suggest? Any help is much appreciated.

Thanks :)

• 0

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +1 I think this can be done without a log factor in $O(n^2 + Q)$. Create a 2D array such that arr[l][r] gives us whether $A_l>A_r$ and $l •  » » 3 years ago, # ^ | 0 If I understand correctly, it works in$O(n^2 + Q\cdot n)$, because you need to iterate over$[l ... r)$. •  » » » 3 years ago, # ^ | ← Rev. 2 → 0 2D prefix sums can also be done in$O(1)$. Here's a simple implementation simple implementation vector>> prefix_sum(n+1, vector>(m+1, mp(0,0))); vector> gridsum(n+1, vector(m+1, 0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x=arr[i][j]; prefix_sum[i][j].first=prefix_sum[i-1][j].first+x; prefix_sum[i][j].second=prefix_sum[i][j-1].second+x; gridsum[i][j]=gridsum[i-1][j-1] + prefix_sum[i][j].first + prefix_sum[i][j].second - x; } } Now you can get 2D prefix sum for$a\le i \le b$and$c \le j \le d\$ by doing gridsum[b][d] - gridsum[b][c-1] - gridsum[a-1][d] + gridsum[a-1][c-1]
•  » » » » 3 years ago, # ^ |   0 You are correct, nice catch.
 » 3 years ago, # |   0 Can you please provide the problem link ?
 » 3 years ago, # |   +1 Here's what you're looking for https://www.youtube.com/watch?v=kPaJfAUwViY&t=1456s (fenwick tree solution)