Overview

Given a specific order in which books are returned to a shelf, the problem asks to compute the total count of books with smaller shelf numbers than the current book, among the books remaining to be returned at each point.

Analysis

In this problem, after returning the \(i\)-th book, we need to count “the number of books with shelf numbers less than \(G_i\)” among the remaining books. If we naively simulate this from the front, we would need to scan up to \(M\) books each time, resulting in an overall time complexity of \(O(M^2)\), which will TLE given the large constraints.

The key observation is that each \(L_i\) represents “how many books among those yet to be returned have a shelf number smaller than the current book’s shelf number.” In other words, if we process from the back, the books we have already seen correspond to “books that will be returned later,” allowing us to manage them efficiently.

Furthermore, if we keep this “list of books yet to be returned” sorted in ascending order by shelf number, we can efficiently determine “the number of books less than \(G_i\)” using binary search.

Algorithm

1. Process the books in reverse order of their return sequence.
2. Prepare a list called books_after, which maintains “books processed so far (= books to be returned later)” in ascending order of shelf number.
3. For each book:
   • For the current book’s shelf number \(G_i\), use binary search to find the number of books in books_after that are less than \(G_i\), and add this to total.
   • Then, insert the current book into books_after (using insort to maintain sorted order).
4. Output the final total.

Example

Consider the following input:

N = 5
M = 4
G = [3, 1, 4, 2]

• Processing from the back:
  • \(i=3\): \(G_3=2\) → books_after=[] → \(L_3=0\), books_after=[2]
  • \(i=2\): \(G_2=4\) → books_after=[2] → \(L_2=1\), books_after=[2,4]
  • \(i=1\): \(G_1=1\) → books_after=[2,4] → \(L_1=0\), books_after=[1,2,4]
  • \(i=0\): \(G_0=3\) → books_after=[1,2,4] → \(L_0=2\), books_after=[1,2,3,4]

The total is \(0+1+0+2=3\)

Complexity

• Time complexity: \(O(M \log M)\)
  (binary search and insertion operations are performed for each element)
• Space complexity: \(O(M)\)
  (size of the books_after list)

Implementation Notes

• By processing from the back, we can efficiently manage “books yet to be returned.”

• Binary search (bisect_left) on a sorted list allows us to quickly find the number of elements satisfying the condition.

• Using insort allows us to insert elements while always keeping the list in sorted order.

  Source Code

import sys
from bisect import bisect_left, insort

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

    # 本の番号を後ろから処理するためのリスト（棚の番号）
    # 後ろから処理して、現在処理中の本以降の本のリストを管理
    books_after = []
    total = 0
    
    # 後ろから処理することで、すでに追加された本がbooks_afterに含まれる
    for i in range(M-1, -1, -1):
        g = G[i]
        # g未満の本の数をカウント (bisect_leftでg未満の要素数を得る)
        idx = bisect_left(books_after, g)
        total += idx
        # 現在の本をリストに追加（次以降の比較対象になる）
        insort(books_after, g)
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.