AtCoder Regular Contest (ARC) 115 E - LEQ and NEQ 解説

atcoder.jp

A をソートしてあいだの範囲に注目して，

  • dp[i+1][j] を， X_i を j 番目の範囲の値にする X_1, \ldots, X_i の場合の数

と定義すると，

  • dp[i+1][j] = len(j) \times \sum_j dp[i][j] - dp[i][j] ( j 番目の範囲は A_i 以下)
  • dp[i+1][j] = 0 (otherwise)

となる．

あとはこれを高速に計算していきたいので，

  • 区間和
  • 各ノードごとに事前に決められた係数 ( len(j)) の倍数を区間加算
  • 区間更新
  • 区間の値を負にする

に対応した遅延セグ木を書くと良い．

時間計算量 O(N \log N)．

atcoder.jp

感想：ずっと定数倍 TLE．頑張って遅延セグ木を非再帰にしてみたものの TLE．ACL を使ってみたら AC．一生懸命育ててきた自分の木を裏切ってしまった感じがしてとても悲しい．ACL 速すぎる．