ABC038-D問題
解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ！ってのとソートの方法を指定する方法についてのメモ。
BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである区間の最大値はO(logN)で求められます。BITは1からaまでの区間についての情報を保持していますが、区間[a, b]について考えたいならセグメントツリーのほうが便利そうです。
http://hos.ac/slides/20140319_bit.pdf
hについて昇順でhが等しかったらwの降順になるようにするソートが必要です。以下のサイトを参考にソートの比較用の関数をつくることで実装しました。他にも構造体で > を定義することで行ったり、ラムダ式を用いる方法でもできそうです。
C++（ソートの補足） - アルゴリズム講習会
