Algoogle

Algorithm for Programming Contest

AOJ 1083 The Incubator

Category: AOJ Tag: binary-indexed-tree

The Incubator

問題概要


以下のクエリをQ個を捌く

  • 新しい個体に番号xを割り当てて列の末尾に入れる
  • 列のx番目の個体を列から取り除く
  • 列のx番目の個体番号を出力する
  • 番号xの個体を列から取り除く

解法


BITで列に入っているかを管理する.
削除はその位置に-1, 追加は末尾に1を加える.
1が立っている位置のうち左からx番目というのは2分探索すれば求まる.
番号xの位置はmapで持って,位置yの番号は配列で持てば良い.

コード


(1083.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,n) repi(i,0,n)

template<class T> class bit {
public:
    vector<T> dat;
    int N;

    bit(){}
    bit(int N) : N(N) { dat.assign(N,0); }
    // sum [0,i)
    T sum(int i){
        T ret = 0;
        for(--i; i>=0; i=(i&(i+1))-1) ret += dat[i];
        return ret;
    }
    // sum [i,j)
    T sum(int i, int j) { return sum(j) - sum(i); }
    // add x to i
    void add(int i, T x) { for(; i < N; i|=i+1) dat[i] += x; }
};


bit<int> bs;
map<int,int> id;
int q, lim, l, r, vs[400010];
bool done[400010];

int get_pos(int p) {
    int lb = l, ub = r, mid;
    while(ub-lb > 1) {
        mid = (lb+ub)/2;
        if(bs.sum(mid) >= p) ub = mid;
        else lb = mid;
    }
    return lb;
}

void normalize() {
    if(bs.sum(r) > lim) {
        while(done[l]) l++;
        done[l] = 1;
        bs.add(l++,-1);
    }
}

void solve() {
    memset(done,0,sizeof(done));
    id.clear();
    l = r = 0;
    bs = bit<int>(q);
    while(q--) {
        int v, x;
        cin >> v >> x;
        if(v == 0) {
            id[x] = r;
            vs[r] = x;
            bs.add(r++,1);
        }
        else if(v == 1) {
            int p = get_pos(x);
            bs.add(p,-1);
            done[p] = 1;
        }
        else if(v == 2) cout << vs[get_pos(x)] << endl;
        else if(v == 3) {
            int p = id[x];
            bs.add(p, -1);
            done[p] = 1;
        }
        normalize();
    }
}

bool input() {
    cin >> q >> lim;
    return q or lim;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    for(int t = 0; input(); t++) {
        solve();
        cout << "end" << endl;
    }
    return 0;
}

Comments