Overview

When returning \(M\) books to shelves in order, for each book we need to find “the number of books that should be returned to shelves with smaller numbers, among the books not yet returned,” and calculate the total sum. This can be reduced to finding the inversion count of a sequence.

Analysis

Understanding the meaning of \(L_i\)

\(L_i\) is “the number of books returned after \(i\) whose shelf number is less than \(G_i\).” Written as a formula:

\[L_i = \#\{j \mid i < j \leq M, \ G_j < G_i\}\]

Reinterpreting the sum

Looking at \(L_1 + L_2 + \cdots + L_M\) as a whole, this counts the number of pairs \((i, j)\) (\(i < j\)) such that \(G_i > G_j\).

\[\sum_{i=1}^{M} L_i = \#\{(i, j) \mid 1 \leq i < j \leq M, \ G_i > G_j\}\]

This is precisely the inversion count of the sequence \(G_1, G_2, \ldots, G_M\).

Concrete example

For example, when \(G = [3, 1, 2]\): - \(L_1\): Among the later elements \([1, 2]\), those less than \(3\) → \(1, 2\), so 2 books → \(L_1 = 2\) - \(L_2\): Among the later elements \([2]\), those less than \(1\) → 0 books → \(L_2 = 0\) - \(L_3\): No books after it → \(L_3 = 0\) - Total: \(2 + 0 + 0 = 2\) (the inversion pairs are \((3,1)\) and \((3,2)\))

Problem with the naive approach

Checking all pairs takes \(O(M^2)\), which is too slow since \(M\) can be up to \(2 \times 10^5\).

Algorithm

We use a Binary Indexed Tree (BIT / Fenwick Tree) to efficiently compute the inversion count.

Procedure: Scan from right to left

1. Prepare a BIT and initialize everything to \(0\). Each position in the BIT tracks “how many books with shelf number \(k\) have been inserted so far.”
2. Process the array \(G\) from the right end (\(i = M-1\)) to the left end (\(i = 0\)).
3. For each \(G[i]\):
   • query(G[i] - 1): Retrieve the count of values already inserted into the BIT that are less than \(G[i]\). This corresponds to \(L_i\) (already inserted = elements to the right of \(i\)).
   • Add this value to the answer.
   • update(G[i]): Insert \(G[i]\) into the BIT.

Since we scan from right to left, the elements in the BIT are “elements to the right of the current position,” and query(G[i] - 1) correctly gives us “the count of values to the right that are smaller than \(G[i]\),” which is exactly \(L_i\).

Complexity

• Time complexity: \(O(M \log N)\) (BIT update and query are \(O(\log N)\) per element)
• Space complexity: \(O(N + M)\) (BIT of size \(N\) and input array of size \(M\))

Implementation Notes

• The BIT’s query returns a prefix sum (from position \(1\) to \(pos\)), so to get the count of values less than \(G[i]\), we use query(G[i] - 1). When \(G[i] = 1\), this becomes query(0) = 0, so it’s safe to add a check for G[i] > 1 or handle the edge case explicitly.

• In Python, when the input is large, reading all at once with sys.stdin.buffer.read() can speed things up.

• BIT indices should be managed as \(1\)-indexed (including \(0\) would cause bit operations to malfunction).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    G = [int(input_data[idx + i]) for i in range(M)]
    idx += M

    # BIT (Binary Indexed Tree) for counting
    # We need suffix counts: for each i, count how many j > i have G[j] < G[i]
    # Sum of L_i = sum over i of (number of j > i with G[j] < G[i])
    # This equals: sum over i of (number of j < i with G[j] > G[i]) ... no, that's inversions in different direction
    # 
    # Actually L_i = number of j in {i+1,...,M} with G[j] < G[i]
    # So total = sum_{i<j} [G[j] < G[i]]
    # This is the number of pairs (i,j) with i < j and G[i] > G[j], i.e., the number of inversions.
    
    # Count inversions using BIT
    # Process from right to left, maintaining counts of values seen so far
    # For each G[i], query prefix sum [1, G[i]-1] to get count of elements already inserted that are < G[i]
    
    bit = [0] * (N + 1)
    
    def update(pos):
        while pos <= N:
            bit[pos] += 1
            pos += pos & (-pos)
    
    def query(pos):
        s = 0
        while pos > 0:
            s += bit[pos]
            pos -= pos & (-pos)
        return s
    
    ans = 0
    # Process from right to left
    for i in range(M - 1, -1, -1):
        g = G[i]
        # Count elements already in BIT with value < g
        if g > 1:
            ans += query(g - 1)
        update(g)
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.