UAPC 2011 J The Incubator

AOJ データ構造

問題

次のようなクエリに答えよ。

  • 先頭の値を削除
  • 末尾に値xを挿入する
  • x番目の値を消去する
  • xの値をもつ要素を消去する
  • x番目の値を答える

制約条件

クエリの数≦40万

方針

普通の配列 + binary indexed tree + map
まだ生きている要素をbinary indexed treeでフラグを立てて管理しておいて、
x番目の要素を削除(or表示)するときは、二分探索。


xの値を持つ要素の削除は、mapでxの値とインデックスを関連づけておいて行う。

ソースコード

int q,lim;
int bit[400001],num[400000],sz,tl;
void add(int i,int x){
	for(;i<=q;i+=i&-i)bit[i]+=x;
}
int sum(int i){
	int ret=0;
	for(;i;i-=i&-i)ret+=bit[i];
	return ret;
}
int get(int x){
	int lo=0, hi=tl, mid;
	while(lo+1<hi){
		mid=(lo+hi)/2;
		if(sum(mid)<x)lo=mid; else hi=mid;
	}
	return lo;
}
int main()
{
	while(scanf("%d%d",&q,&lim),q){
		memset(bit,0,sizeof(bit));
		map<int,int> pos;
		sz=tl=0;
		rep(it,q){
			int query,x; scanf("%d%d",&query,&x);
			
			if(query==0){
				pos[x]=tl;
				num[tl++]=x;
				add(tl,1);
				if(sz>=lim){
					add(get(1)+1,-1);
				}
				else sz++;
			}
			if(query==1){
				add(get(x)+1,-1);
				sz--;
			}
			if(query==2){
				printf("%d\n",num[get(x)]);
			}
			if(query==3){
				add(pos[x]+1,-1);
				sz--;
			}
		}
		puts("end");
	}
	return 0;
}