Overview

At each point in time, we count “among the books yet to be returned, how many go to a shelf with a smaller number than the shelf we just returned a book to,” and find the total sum. This is equivalent to counting the inversion count of the array \(G\).

Analysis

\(L_i\) is “the number of values among those after position \(i\) (\(i+1..M\)) that are smaller than \(G_i\).” In other words, [ L_i = |{j \mid i G_j}| ] which is exactly the inversion count of \(G\).

Why the naive solution is too slow

If for each \(i\) we scan all elements to the right and count “smaller ones,” in the worst case: - At \(i=1\), we check \(M-1\) elements - At \(i=2\), we check \(M-2\) elements - …

The total is \(O(M^2)\), which is too slow for \(M \le 2\times 10^5\).

How to solve it

We maintain the “occurrence counts of values on the right side” in a data structure, and for a given value \(x\), we need to efficiently answer: - “How many values are \(x-1\) or less?” (= count of values less than \(x\))

For this, we use a Fenwick Tree (BIT).

Algorithm

The BIT holds “the count of shelf numbers already seen (= on the right side),” and we scan \(G\) from right to left.

• When examining \(x = G_i\) from right to left, \(G_{i+1},\dots,G_M\) are already registered in the BIT
• Therefore, \(L_i\) is “the count of registered values less than \(x\)”: [ L_i = \text{BIT.sum}(x-1) ]
• After that, add the current \(x\) to the BIT (occurrence count +1): [ \text{BIT.add}(x, 1) ]

Small example

For \(G=[3,1,2]\) (processing from right to left): - See \(2\): nothing on the right → count of \(<2\) is 0; add(2) - See \(1\): right side has {2} → count of \(<1\) is 0; add(1) - See \(3\): right side has {1,2} → count of \(<3\) is 2; add(3)

Total is \(2\) (the inversions are (3,1) and (3,2), giving 2).

Complexity

• Time complexity: \(O(M\log N)\) (for each element, BIT addition and prefix sum are each \(O(\log N)\))
• Space complexity: \(O(N)\) (BIT array)

Implementation Notes

• It is standard practice to implement BIT as 1-indexed, so we can use the shelf numbers \(G_i\) (\(1..N\)) directly.

• “Count of values less than \(x\)” is obtained by sum(x-1) (note that sum(x) would give “count of values less than or equal to \(x\)”).

• The answer can be as large as \(M(M-1)/2\), so depending on the language, 64-bit integers may be needed (Python handles this automatically).

  Source Code

import sys

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    G = data[2:2+M]

    fw = Fenwick(N)
    ans = 0
    for x in reversed(G):
        ans += fw.sum(x - 1)
        fw.add(x, 1)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.