IOI 2015 day1 - Teams
解法
$ (A_i, B_i)を二次元平面上の点に対応させる
矩形領域の総和取得 : Wavelet Matrix, 永続 segtree で$ O(\log N)
簡単のため全ての$ y座標は異なるとし、$ K_iが狭義短調増加であるとする。
$ iの小さい順に$ K_i点ずつマッチングさせていく。$ iにおける処理は、$ x座標が$ K_i以下かつ$ y座標が$ k_i以上の点のうち、マッチングされず残っているものを$ y座標が小さい順にマッチングさせていけばよい。
各区間$ K_{i - 1} < x \leq K_iについて、マッチングされた（あるいは使えない）点の$ y座標の最大値を$ Y_iとおくと、これは単調減少である。
$ Y_iが同じ区間はマージすることを考えると、ならし$ O(M\log N)で解くことができる。（説明が難しいので省略）
感想
『いつもの』の組み合わせ
データ構造力💪