AOJ0343 プログラミングコンテスト II

問題ページ
Programming Contest II | Aizu Online Judge

解法

(点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧してBIT上での二分探索を用いることでできる。

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

ソースコード

平衡二分探索木

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<typename T>
using btree = tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  btree<PII> tr;
  FOR(i, 1, n+1) tr.insert({0, -i});
  REP(i, c) {
    int type;
    cin >> type;
    if(type == 0) {
      ll t, p; cin >> t >> p;
      tr.erase({sc[t], -t});
      sc[t] += p;
      tr.insert({sc[t], -t});
    } else {
      ll m; cin >> m; m--;
      cout << -tr.find_by_order(m)->second << " " << tr.find_by_order(m)->first << endl;
    }
  }

  return 0;
}

BIT

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

// Binary Indexed Tree
// 0-indexed
template <typename T>
struct BIT {
  vector<T> bit;
  int neutral = 0, n;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
                   g = [](const T l, const T r) -> T { return l+r; };

  // 初期化
  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_ = 1e5) { n = n_+1; bit.assign(n_+1, neutral); }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < n; x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i)に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
  // 合計がw以上の最小の位置 O(log^2 n)
  int lower_bound(T w) {
    int lb = -1, ub = n;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(query(mid) >= w) ub = mid;
      else lb = mid;
    }
    return ub;
  }
};

ll type[100010], a[100010], b[100010], sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  vector<pair<ll,ll>> v;
  for(int i=0; i<c; ++i) {
    cin >> type[i];
    if(type[i] == 0) {
      cin >> a[i] >> b[i];
      sc[a[i]] += b[i];
      v.push_back({sc[a[i]], -a[i]});
    } else {
      cin >> a[i];
    }
  }

  // (点数、チーム番号)のpairを番号つける
  for(int i=1; i<=n; ++i) v.push_back({0, -i});
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  reverse(v.begin(), v.end());

  map<pair<ll,ll>,ll> p2n;
  vector<pair<ll,ll>> n2p;
  int idx = 0;
  for(auto i: v) {
    p2n[i] = idx++;
    n2p.push_back(i);
  }

  BIT<ll> bit(n2p.size());
  for(int i=1; i<=n; ++i) bit.update(p2n[{0, -i}], 1);

  memset(sc, 0, sizeof(sc));
  for(int i=0; i<c; ++i) {
    if(type[i] == 0) {
      bit.update(p2n[{sc[a[i]], -a[i]}], -1);
      sc[a[i]] += b[i];
      bit.update(p2n[{sc[a[i]], -a[i]}], 1);
    } else {
      int ret = bit.lower_bound(a[i]);
      cout << -n2p[ret].second << " " << n2p[ret].first << endl;
    }
  }

  return 0;
}