第二回日本最強プログラマー学生選手権 F Max Matrix
タイプ$ 2のクエリについてのみ考える(タイプ$ 1のクエリも同様にして処理できる).
タイプ$ 2のクエリは次のように言い換えられる.
「$ a_k < max(b_j, Y_i)なる$ kについて, $ Y_i - max(a_k, b_j)をスコアに加算する」
これは$ Y_iの部分と$ max(a_k, b_j)の部分に湧けて考えることによってBITによって高速に解ける形に分割することが可能である. $ Y_iが大きいので座標圧縮する必要があることに注意.