BIT上の二分探索
yukicoder.me 類題がこれとこれ。 coonevo.hatenablog.com coonevo.hatenablog.com 上記の類題と違うのは値の範囲が広いこと。こういうやつはクエリ先読みすると種類数が少ないから順序データに座標圧縮すればよい。あとはライブラリでやるだけ。 座圧のうま…
atcoder.jp 類題がこれ。 coonevo.hatenablog.com ライブラリでやるだけ。 template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(N+1, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[</t></typename>…
コンテスト参加記はこちら。 coonevo.hatenablog.com D - Multiset 問題概要 解説 D - Multiset 問題へのリンク 問題概要 集合の初期状態が与えられる。 以下2つのクエリを処理したあと、残っている要素のいずれかを出力せよ(空の場合は-1)。 要素を追加。…