#yukicoder391C ''' この問題は簡単すぎたので(迫真) はやくこれになりたい うそです 解いたことありました 設問が難解 これがyukicoder なるほど順列か Li,Riを順列に差し替えるのか そして差し替え規則は一定、と。なんとなく理解してきた。 つまり(B1,C1), ... ,(Bn,Cn)を順列通りに並び替えるから、転倒数の総和を数えろ。 って問題になるわけだ。 より簡単な問題から考察しよう。 数字を範囲ではなく固定値として扱う場合は? ■AfterContest Dに注力する判断は正しかった、と思う。Cも解こうか。 各数字ごとに転倒への寄与を考えたいところではある。 実装地獄になったんですけど・・・ SegTreeとLazySegTreeの2本を生やして殴る、ほんとうにこれでいいんですか 一旦ライブラリを貼る。 ''' #Segment Tree: O(logN) class SegmentTree: # Segment Tree def __init__(self,n,identity_e,combine_f): # 適応条件: 単位元eがある、互換可能 self._n=n; self._size=1 # モノイド(単位元)の例: while self._size>=1 # self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1]) # def fold(self,L,R): # fold: 区間取得 O(logN) L+=self._size; R+=self._size # 区間 [L,R) の特定値を取得する vL,vR=[self._identity_e]*2 # while L>=1; R>>=1 # .R.5 L 7 Rの移動が変則的 return self._combine_f(vL,vR) # ←R L→ ''' 値xにおいて、x未満を取る値がいくつあるか?で転倒数への寄与を計算する。 Ei: Aiがx未満になる期待値 Fi: Aiが丁度xになる期待値 とすると、Ai,Ajが転倒する期待値は Fi * Ej * NP2 * (N-2)! : Aiが丁度xを取り、Ajがx未満を取る。それ以外の順番は不定 となる。あとはこれをベースに式を圧縮する。 L=x となる半開区間[L,L+d)において、答えへの寄与度を計算する。 W: 区間数: この閉区間内で、Ai=xとなるAiの個数 X: sum(Fi): 丁度Ai=xとなる期待値の総和 Y: sum(Fi*Ei): Ai=xを取るAiについて、Ai