AtCoder Beginner Contest 127 F - Absolute Minima

コンテスト中はＥに時間を全て使ってしまいました。

自分の理解した範囲で解説していくので、間違いなどありましたら指摘して頂ければ

嬉しいです。

考えたこと

・ｂは本質ではない！順番に足していけばよい！

・絶対値の和の関数の最小値を取る座標は、傾きの変わる点の中央値！（典型）

・以下、aの中央値を求めることを主に考える。

・中央値を効率的に求めるアルゴリズムは知りませんが、Ｋ番目を求めるアルゴリズムは知っている！

参考：けんちょん様

k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など

https://qiita.com/drken/items/1b7e6e459c24a83bb7fd

・しかし、今回の場合はＫ番目のＫの値が変化していく。（Ｋ＝Ｎ／２番目）

なので、上の記事に載っているpriority_queueを二つ使う方法はだめ？

（－＞解答ではpriority_queueで解いています。）

・となると、上の記事に載っているＢＩＴを使った解法でないと無理そう？

ー＞実装力がないため、実装出来ず・・・

解答を見た。

priority_queueを二つ(ql,qrとする)使う方法で解けるらしい。

小さい方半分をｑｌ、大きい方半分をｑｒに管理させる。

真ん中（Ｎ／２番目）から自由に値を取り出したいので、qrを

最小値が取り出せるようにする。(priority_queue<int,vector<int>,greater<int>>を使う)

qlは最大値を取り出す通常のpriority_queueを使う。

こうすることで、中央値の値（Ｎ／２番目）はqlの最大値ql.top()として自由に取り出せるようになった。

editorialではaを２つ追加することで実装を楽にしているそうだが、私はかえって混乱してしまったので素直な１つずつ追加する実装を以下に示す。

注意点：

・aの個数が奇数個のとき、中央値がqlの側に来るように（qlから答えの座標を取り出したいため）、qlはqrよりも１つ大きいかあるいは等しい状態に保つようにする。

・sumaは絶対値部分の答えの和を、sumbはｂの和を表すことにする。

ー＞sumaには追加クエリ毎に、追加前の絶対値の和の最小値と追加後の絶対値の和の最小値の差分を足している。

ー＞aが前回の最小値区間内に含まれる場合、追加後の最小値の座標も最小値区間に含まれるため、変化するのは０。（ｂの変化分はある）

ー＞aが区間外の場合、追加後の最小値の座標は、追加前の最小値の区間の端点のうちaに近い方となる。よって変化するのはbと、最小値の座標の変化分となる。

実装

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;

signed main() {
  int Q;
  cin >> Q;

  int suma = 0, sumb = 0;
  priority_queue<int> ql;
  priority_queue<int, vector<int>, greater<int>> qr;

  ql.push(-INF);
  qr.push(INF);

//while(Q--)を使うと変数iが使えるのでお勧め（余談）
  while (Q--) {
    int q;
    cin >> q;

    if (q == 1) {
      int a, b;
      cin >> a >> b;
      sumb += b;
      
      if (ql.size() == qr.size()) {
          //前回の最小値の区間内にある時、増加分は０
        if (ql.top() <= a && a <= qr.top()) {
          suma += 0;
        } else {
          //aが前の最小値の区間の範囲外にあるとき。
          //このとき、次の最小値は区間の端のうち、追加する点に近い方になる。
          //よって増加分は近い方の端点との距離。
          suma += min(abs(ql.top() - a), abs(a - qr.top()));
        }
      } else {
        suma += abs(ql.top() - a);
      }
      
      if (qr.top() <= a) {
        qr.push(a);
      } else {
        ql.push(a);
      }

      //qrと比べて、qlが１大きいか等しい状態に保つ。
      if (qr.size() > ql.size()) {
        ql.push(qr.top());
        qr.pop();
        //qlがqrより２大きいとき
      } else if (ql.size() > qr.size() + 1) {
        qr.push(ql.top());
        ql.pop();
      }

    } else if (q == 2) {
      cout << ql.top() << " " << suma + sumb << endl;
    }
  }

  return 0;
}

感想：

もう少し実装力を付けたいです。