AOJ : 1083 - The Incubator

AOJ データ構造

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1083
日本語の問題文なので, 説明は省略です.

アルゴリズム

セグメント木を使うことで解くことができます.
解くときにメモったのをそのまま貼りつけただけ↓


セグメント木

  • 配列のxi番目を処理したいときに使用
  • dat[] : セグメント木のデータ
    • 各ノードは, int型で範囲の要素数を管理
  • size : dat配列のリーフの何番目まで埋まってるか
    • low以上の値とする
  • 要素の追加処理 add(int x)
    • xの番号の個体のノードを配列の最後へ追加する処理
    • size++;
    • lim--;
  • 要素の検索処理 find(x)
    • 配列x番目のノードがdat配列の何番目に入っているかを求める
  • 要素の削除処理 erase(int pos)
    • dat[pos]からルートまでのぼりながら, 各ノードをデクリメント
    • lim++;

マップ map

  • 個体番号x番目を処理したいときに使用
  • key : 個体番号
  • val : セグメント木のdat配列の何番目にデータ格納したか
  • 個体番号xi番目を追加したときは, map[xi] = size;
  • 個体番号xi番目を削除したときは, 特に何もする必要なし

プログラム

typedef pair<int,int> P;

int dat[1<<20+2]; //セグメント木
int low = 1<<19-1; //リーフノードの最小インデックス

int q,lim;
int size;
map<int,int> num;
int rnum[400000];

//個体番号xのノードを追加する処理
void add(int x){
  num[x] = size;
  dat[size] = 0;
  rnum[size-low] = x;

  lim--;
  size++;

  int pos = size - 1;

  //ルートノードまで登りながら, 各ノードをインクリメント
  while(0 < pos){
    dat[pos]++;
    pos = (pos - 1) / 2;
  }
}

//配列のx番目が, dat配列の何番目か求める
int find(int x){
  int pos = 0;

  //左にもぐるか, 右にもぐるか決めつつ, リーフまでもぐる
  while(pos < low){
    int left = pos * 2 + 1;
    int right = pos * 2 + 2;

    if(x <= dat[left]){
      pos = left;
    }
    else{
      x -= dat[left];
      pos = right;
    }
  }

  return pos;
}

//dat配列のpos番目を削除する処理
void erase(int pos){
  lim++;

  while(0 < pos){
    dat[pos]--;
    pos = (pos - 1) / 2;
  }
}

int main(void){
  while(scanf("%d%d",&q,&lim),q||lim){
    memset(dat,0,sizeof(dat));
    memset(rnum,0,sizeof(rnum));
    num.clear();
    size = low;

    while(q--){
      int query,x;
      scanf("%d%d",&query,&x);

      if(query == 0){
        add(x);
        if(lim < 0){ //もし, 個体の数がlimを超えたら, 配列の0番目を削除
          int pos = find(0);
          erase(pos);
        }
      }
      else if(query == 1){
        int pos = find(x);
        erase(pos);
      }
      else if(query == 2){
        int pos = find(x);
        printf("%d\n",rnum[pos-low]);
      }
      else if(query == 3){
        int pos = num[x];
        erase(pos);
      }
    }

    printf("end\n");
  }
}