概要

製品の品質スコア \(A_i\) をもとに、各検査の基準値 \(T_j\) 未満の「まだ廃棄されていない」製品をすべて廃棄するとき、各検査で新たに廃棄される個数を求めます。

考察

各検査で「残っている製品」を毎回走査して条件判定すると、最悪で \(O(NQ)\) となり \(2\times 10^5\) では間に合いません。

重要な観察は次の2つです。

1. 廃棄されるのはスコアが小さい方から連続的
   ある時点で基準値が \(x\) なら、廃棄済みの製品は「スコアが \(x\) 未満のもの全部」です（並べ替えて考えると先頭から何個、という形になる）。

2. 過去より小さい基準値は意味がない
   例えば過去に \(T=10\) で検査してスコア \(<10\) を全て捨てた後、次に \(T=5\) が来ても追加で捨てられるものはありません。
   つまり実際に効いてくるのは、これまでの基準値の最大値 \(cur=\max(T_1,\dots,T_j)\) だけです。

よって、「これまでに廃棄された個数」を管理しておき、基準値が更新（増加）されたときだけ追加分を計算すればよいです。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. 変数を用意する：
   • \(cur\)：これまでに有効だった基準値の最大（初期値は \(-1\)）
   • \(removed\)：これまでに廃棄された個数（初期値 \(0\)）
3. 各検査で基準値 \(t\) を読む：
   • もし \(t \le cur\) なら、追加の廃棄は起きないので答えは 0。
   • そうでなければ、ソート済み \(A\) に対して
     bisect_left(A, t)（\(t\) 以上が初めて現れる位置）を求める。
     これは「スコアが \(t\) 未満の製品の個数」＝ \(new\_removed\) を表す。
     • 今回新たに廃棄された個数は \(new\_removed - removed\)。
     • \(removed \leftarrow new\_removed,\ cur \leftarrow t\) と更新する。

具体例

\(A=[3,1,8,6,2]\) をソートすると \([1,2,3,6,8]\)。

• \(t=4\)：\(<4\) は 3個（1,2,3）なので新規廃棄は \(3-0=3\)
• \(t=7\)：\(<7\) は 4個（1,2,3,6）なので新規廃棄は \(4-3=1\)
• \(t=5\)：\(5 \le 7(=cur)\) なので新規廃棄は 0

計算量

• 時間計算量: ソートに \(O(N\log N)\)、各検査で二分探索に \(O(\log N)\) を行うので合計 \(O(N\log N + Q\log N)\)
• 空間計算量: ソート済み配列などで \(O(N)\)

実装のポイント

• bisect_left(A, t) は「\(t\) 未満の個数」を直接返すので、差分 new_removed - removed を出力します（累計を出してしまうと不正）。

• 基準値が下がったときは必ず 0 個になるため、cur（これまでの最大基準値）を持って t <= cur を判定します。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys
from bisect import bisect_left

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    A = [next(it) for _ in range(N)]
    A.sort()

    cur = -1
    removed = 0
    out = []

    for _ in range(Q):
        t = next(it)
        if t <= cur:
            out.append("0")
        else:
            new_removed = bisect_left(A, t)
            out.append(str(new_removed - removed))
            removed = new_removed
            cur = t

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。