BoB005-E: Discard This Card

2 secs 1024 MB
kyaneko999's icon kyaneko999

解説

クエリは以下のように言い換えられます.

  • Ti=0T_i=0 のとき,j>ij>i かつ Tj=1T_j=1 を満たすような jjj1,j2,,jkij_1,j_2,\dots,j_{k_i} とする.max(Xj1,Xj2,,Xjki)\max(X_{j_1},X_{j_2},\dots,X_{j_{k_i}}) を答えよ.

クエリを順番に処理する場合,ii 番目のクエリでは最大で QiQ-i 個の jj をチェックする必要があるため,全体の計算量は O(Q2)O(Q^2) となり TLE してしまいます.
そこで,クエリを逆順に処理することを考えると,クエリは以下のように解釈することができます.

  • 最初 Sakky さんはカードを 11 枚も持っていない.
  • Ti=0T_i=0 のとき,現在持っているカードに書かれた数のうち,値が最大のものを答える.
  • Ti=1T_i=1 のとき,XiX_i が書かれたカードを持ち札に加える.

この解釈のもとでは,「現在持っているカードに書かれた数のうち,値が最大のもの」を更新しながらクエリを処理することで,計算量は O(Q)O(Q) に抑えられます.

解答例(Python)

別解を紹介します.
まず,クエリをすべて先読みすることによって,最初に Sakky さんが所持しているカードを求めます.
その後,Python の heapq や C++ の multiset を用いて手札の更新と最大値の取得を行いながらクエリを順番に処理します.
この方法では O(QlogQ)O(Q\log Q) の計算量で問題を解くことができます.

解答例(Python)