BOJ 27551 - Vrsta

BOJ 27551 - Vrsta

단순히 세그먼트 트리를 써서 구간합을 이분탐색으로 찾아주거나 K번째 수를 찾는 테크닉으로 $O(N \log N)$ 이나 $O(N \log ^2N)$ 에 풀 수 있다.

void solve() {
   int n;
   cin >> n;
   vector<pi> qry(n);
   vi val;
   for (auto &[v, a]: qry) cin >> v >> a, val.pb(v);
   uniq(val);
   for (auto &[v, a]: qry) v = lbi(val, v);
   fenwick<int> fenw(sz(val) + 1);
   ll sum = 0;
   for (auto &[v, a]: qry) {
      sum += a;
      ll pivot = (sum + 1) / 2;

      fenw.update(v, a);

      int l = 0, r = sz(val) - 1, ret = -1;
      while (l <= r) {
         int m = l + r >> 1;

         ll s = fenw.query(0, m);
         if (s >= pivot) ret = m, r = m - 1;
         else l = m + 1;
      }
      cout << val[ret] << endl;
   }
}