Overview

This problem asks us to record, for each book in the order they are returned to shelves, the count of not-yet-returned books whose shelf number is smaller than the current book’s shelf number, and find the total sum of these counts.

Analysis

At the timing each book is returned, we need to find the count (\(L_i\)) of books that will be returned later whose shelf number is smaller than the current book’s. A naive approach would examine all subsequent books for each book, resulting in \(O(M^2)\) time complexity, which exceeds the time limit since \(M\) can be up to \(2 \times 10^5\).

To solve this efficiently, the following observations are important: - Process the books in reverse order (from back to front) - Efficiently manage the occurrence count of each shelf number - Use a data structure (Fenwick Tree) that can handle range queries quickly

Algorithm

1. Process the books in reverse order (\(i = M-1, M-2, ..., 0\))
2. Use a Fenwick Tree (Binary Indexed Tree) to manage the occurrence count of each shelf number
3. For each book \(i\):
   • Use the Fenwick Tree to retrieve the sum of occurrence counts for shelf numbers smaller than the current shelf number \(g_i\) (from \(1\) to \(g_i-1\))
   • Add that value to the running total
   • Increment the occurrence count of the current shelf number \(g_i\) by 1 in the Fenwick Tree
4. Output the final total

By processing in reverse order, at the time each book is processed, the Fenwick Tree contains information only about “already processed books” (which are later books in the original order), correctly maintaining the information about “subsequent books” that we want.

Complexity

• Time complexity: \(O(M \log N)\)
  • Each book’s processing requires \(O(\log N)\) for Fenwick Tree update and query operations
  • We process \(M\) books in total
• Space complexity: \(O(N)\)
  • The Fenwick Tree size is proportional to the number of shelves \(N\)

Implementation Notes

• In the Fenwick Tree implementation, note that indices start from 1

• Query processing should only be performed when \(g_i > 1\) (when \(g_i = 1\), \(g_i-1=0\) which is out of query range)

• Use sys.stdin.read() for efficient input reading

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    G = list(map(int, data[2:2+m]))
    
    fenwick = [0] * (n + 2)
    
    def update(index, delta):
        while index <= n:
            fenwick[index] += delta
            index += index & -index
            
    def query(index):
        s = 0
        while index > 0:
            s += fenwick[index]
            index -= index & -index
        return s
    
    count = [0] * (n + 1)
    total = 0
    
    for i in range(m - 1, -1, -1):
        g = G[i]
        if g > 1:
            total += query(g - 1)
        update(g, 1)
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.