AOJ 1083 - The Incubator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1083

解法

Segment Tree っぽいデータ構造を使って，各クエリに O(log Q) 程度で答えられるようにする．

まず個体の番号をインキュベートした順に番号を割り当て直し，map と配列でそれぞれの対応をつけておく． こうすることで，個体の番号は高々 Q で，「配列」中の個体番号は常に昇順 になる．

葉が Q 個以上あるような完全二分木で，その番号の区間のうちいくつの要素が「配列」の中にあるか，という区間和を管理する． インキュベートするときは +1，円環の理に導くときは -1 すればいい． また，この二分木の根は「配列」の中にある個体の数を表しているので，limit を越えているかどうかはここをチェックすればいい．

「配列」の n 番目を見付けるときは，n とその区間の子ノードの区間和の大小関係で辿っていける．

  1 #include <cstdio>
  2 #include <map>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 struct Incubator
  7 {
  8   static const int H = 20;
  9   static const int BASE = (1<<(H-1));
 10   int tree[1<<H];
 11   int limit;
 12   map<int,int> m;
 13   int rev[400000];
 14 
 15   void init(int l)
 16   {
 17     fill_n(tree, 1<<H, 0);
 18     fill_n(rev, 400000, -1);
 19     limit = l;
 20     m.clear();
 21   }
 22 
 23   void add(int idx, int v)
 24   {
 25     while (idx != 0) {
 26       tree[idx-1] += v;
 27       idx >>= 1;
 28     }
 29   }
 30 
 31   void incubate(int x)
 32   {
 33     if (tree[0] == limit) {
 34       enkan_idx(0);
 35     }
 36     const int i = m.size();
 37     m[x] = i;
 38     rev[i] = x;
 39     add(i + BASE, 1);
 40   }
 41 
 42   void enkan(int x)
 43   {
 44     add(m[x] + BASE, -1);
 45   }
 46 
 47   void enkan_idx(int n)
 48   {
 49     add(find(n), -1);
 50   }
 51 
 52   int query(int n) const
 53   {
 54     return rev[find(n) - BASE];
 55   }
 56 
 57   int find(int n) const
 58   {
 59     int idx = 1;
 60     while (idx < BASE) {
 61       const int l = idx<<1;
 62       const int r = l+1;
 63       if (n < tree[l-1]) {
 64         idx = l;
 65       } else {
 66         idx = r;
 67         n -= tree[l-1];
 68       }
 69     }
 70     return idx;
 71   }
 72 };
 73 
 74 int main()
 75 {
 76   static Incubator qb;
 77   int Q, L;
 78   while (scanf("%d %d", &Q, &L) != EOF && Q != 0) {
 79     qb.init(L);
 80     for (int i = 0; i < Q; i++) {
 81       int q, x;
 82       scanf("%d %d", &q, &x);
 83       switch (q) {
 84         case 0:
 85           qb.incubate(x);
 86           break;
 87         case 1:
 88           qb.enkan_idx(x-1);
 89           break;
 90         case 2:
 91           printf("%d\n", qb.query(x-1));
 92           break;
 93         case 3:
 94           qb.enkan(x);
 95           break;
 96       }
 97     }
 98     puts("end");
 99   }
100   return 0;
101 }