price_trie.cpp

// double 12345.67 -> int 1234567

struct Trie {
  std::array<int, (size_t) 1.1e7> cnt, sum;

  void update(int price, int qty) {
    int cnt_delta = qty ? (cnt[price] ? 0 : +1) : (cnt[price] ? -1 : 0);
    int sum_delta = qty - sum[price];
    for (int node = 0, tmp = price, p10 = 1e7; p10; tmp %= p10, p10 /= 10) {
      node = 10 * node + tmp / p10;
      cnt[node] += cnt_delta;
      sum[node] += sum_delta;
    }
  }

  int kth(int k) {
    int node = 0;
    for (int i = 0; i < 7; i++) {
      int next_d = (i == 0);
      for (; cnt[10 * node + next_d] < k; next_d++) {
        k -= cnt[10 * node + next_d];
      }
      node = 10 * node + next_d;
    }
    return node;
  }

  int min() { return kth(1); }
  int max() { return kth(cnt[0]); }

  Trie() {
    cnt.fill(0);
    sum.fill(0);
  }
};