クエリの先読みをすることでカードの得点として現れる値を小さい方から \(d_1,d_2,\ldots,d_k\) とし(座標圧縮)、\(i\) 番目の値が \(d_i\) に対応するFenwick Tree(あるいはセグメント木)を使ってクエリを処理します。
具体的には、「各得点に対応するカードの枚数を管理するFenwick Tree \(X\)」と「各得点に対応するカードの枚数と得点の積を管理するFenwick Tree \(Y\)」を使います。\(1, 2\) 種類目のクエリによる更新は簡単です。\(3\) 種類目のクエリに対しては、まず \(X\) における \([l, k)\) 内の総和が与えられた \(x\) を超えないような最小の \(l\) を求め、\(Y\) における \([l, k)\) 内の総和を答えに加算します。そして、残りを \(d_{l-1}\) から選ぶことで所望の値を求められます。
\(N=Q\) として計算量を考えます。最悪の場合は各クエリにおいて二分探索を行い、さらに内部でFenwick Treeの取得クエリを使っているので \(\mathrm{O}(N (\log N)^2)\) となります。また、セグメント木上の二分探索(AtCoder Libraryでは \(\mathrm{min\_left}\) として提供されています)を用いると \(\mathrm{O}(N \log N)\) となります。