座標圧縮してfenwick_treeで数え上げるやつ
某動画を見て以来（初めて見たとき茶コーダーとか）どういうことなんだろうって思ってたやつ 忘れないように
何がしたいの
i<jかつA_i<A_jを満たすような組み合わせの数え上げ
例：
A={1,1000,10,10}
→(0,1),(0,2),(0,3)で3つ（例がカスかもしれん・・・）
前提知識
座標圧縮
配列があって，要素が小さい順に（でかい順に振ることもあるのかな知らない）番号を振るやつ
例：
A={1,1000,10,10}
→{0,2,1,1}
fenwick_tree
segment treeの簡易版みたいな奴らしい 一点更新と区間和取得ができたりする 自分の構築次第でfenwick_tree上で二分探索とかできる（とりあえず今回はAtCoder Libraryのやつをまんま使う）
fw.add(x,p):a[x]+=p
fw.sum(l,r):a[l]+a[l+1]+...+a[r-1]
どうするの
1.長さnのfenwick_treeを宣言しておく
2.座標圧縮する
3.0から座標圧縮で対応するところまでの区間和を取得して現在の答えに足す(fw.sum(0,k)みたいな）
4.座標圧縮で対応するところに1足す(fw.add(k,1)みたいな）
5.3-4を最後まで繰り返す
イメージ
4がカウントしてるとみなすと良さそう
要素を順番に追加しながら操作してるのでi<jの順序関係はこれで満足してて，自分のところより小さいのを数えてやればA_i<A_jとなってるのをめでたくいい感じに数えられて，最高！
実際にやってみよう
ABC187 B - Gentle Pairs
つい先日開催されたABCのB問題ですが，これを使って解くことができます．
解法
まず，満たすべき傾きの条件-1<=(y_j-y_i)/(x_j-x_i)<=1は，abs(y_j-y_i)<=abs(x_j-x_i)と同値でした．故にこれを満たすような(i,j)の個数を求めてやる必要があります．
これの絶対値をそのまま外そうとすると，左辺の絶対値の中身の正負，右辺の絶対値の中身の正負の場合わけで４通りのパターンが出てしまいます．
しかしここでよくよく考えてみると，最終的な点のプロット状況が決まれば，入力で与えられるi,jの順番自体はどうでもいいことが分かります．（結局言わんとしてるのは傾きの絶対値が１以下になるような直線をできるだけたくさん結べってだけなので）
よって，i<jならばx_i<x_jとみなしても差し支えないことがわかります．そうすると右辺の絶対値の中身が必ず正になるので場合分けが２通りですみます．
そうしてそれぞれの場合で式を展開して変形してみると，以下のようになるかと思います．
(i)(y_i<=y_j) and (x_i-y_i)<=(x_j-y_j)
(ii)(y_i>=y_j) and (x_i+y_i)<=(x_j+y_j)
とりあえず変数が散らばってるのは気持ち悪いので一方の辺に寄せてみました．これを見てみるとx+y,x-yと言う形が見えるかと思います．ここから45度回転が見えるのでx'=x-y,y'=x+yとして45度回転させてみます．（賢い方はここの辺りの考察が無くても図から回転させる発想が出てたかもしれないですが）
そしてさらに先ほど言った平面上の点はどのような順番で見ても問題ないと言うところからi<jならばx'_i<x'_jになるようにindexを振ってやると，結局ある頂点から見たときにこんな区画にいるような頂点との組み合わせが条件を満たすと言うことがわかります．
雑な手書きでごめんなさい．
あとはx',y'それぞれについて座標圧縮して，あるx'=x'_kまで要素を追加したらx'=x'_k上の各点について上のような状況を満たす点の個数をカウントしてやればいいです．これは，ある点vのx’座標，y'座標を圧縮した結果をそれぞれx'_v,y'_vとすれば，fw.add(y'_v,1)をx'=x'_vを満たす各点について行なった後に，さらにそれぞれの点についてfw.sum(0,y'_v+1)-1としてやればよさそうです．（-1は自分を除く）
座標圧縮にO(NlogN),各要素の追加や総和を求めるごとにO(logN)なので，結局O(NlogN)でこの問題を解くことができます．
本来の想定解法はO(n^2)なので，めちゃめちゃ高速になってるのがわかります．（制約が小さいので，あまり数字には出て来づらいのですが） ただABC-Bでこのレベルを求められたらちょっと参りますね・・・
また今回学ぶにあたって色々な方々の提出を拝見させていただきました．皆さまありがとうございました．
