ARC 033 C - データ構造

問題

問題概要

タイプ 1 ： S に数 X を追加する。 タイプ 2 ： S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。 この２つを高速に行うことができるデータ構造を使えばよい。

解法

今回の問題は、Xがあまり大きくない。よって、バケットソートの要領でsegtreeを使った。seg[k + size - 1]に、X=kがいくつあるかを格納していくことにする。タイプ1の場合、seg[k + size - 1]をインクリメントして、上のノードに対してもそれを反映させながら、区間の和を更新していけばよい。タイプ2の場合、二分探索を使用して求める。x番目に小さい数というのは、求める数より小さい数が、x個あるということなので、segに入っている区間の和を利用すれば求める数を計算できる。

ミス

今回使用したseg木は、区間の和をもっていて、任意の場所をインクリメントまたは、デクリメントすることができる。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

const int MAX_N = 1 << 18;
int size;
ll seg[MAX_N * 2];//segは欲しい情報
struct segtree{
    segtree(int n){
        size = 1;
        while(size < n) size *= 2;//要素数を2のべき乗に
    }
 
    void update_add(int k){//k番目の値を　1増やす
        k += size - 1;
        seg[k]++;
        //上りながら更新
        while(k > 0){
            k = (k - 1) / 2;
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; //子の和を入れていく
        }
    }
    void update_dic(int k){//k番目の値を　1増やす
        k += size - 1;
        seg[k]--;
        //上りながら更新
        while(k > 0){
            k = (k - 1) / 2;
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; //子の和を入れていく
        }
    }
    //[a, b)の和を求める
    ll query(int a, int b, int k = 0, int l = 0, int r = size){
        if(r <= a || b <= l) return 0;//和に影響を与えない 0
        if(a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);//左の子の和
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);//右の子の和
        return x + y; //和
    }
};


int q;
int main(void){
    segtree st(200000);
    cin >> q;
    rep(i, q){
        int t; cin >> t;
        int x; cin >> x;
        if(t == 1){
            st.update_add(x);
        }else{
            int l = 1; int r = 200001;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(st.query(0, mid) < x) l = mid;
                else r = mid;
            }
            printf("%d\n", l);
            st.update_dic(l);
        }
    }
    return 0;
}