AOJ1083 The Incubator

データ構造弱いので書いてみようかなと思ってやった。
BITかいて適当にほげほげする。クエリ先読みした（罪悪感）
はじめてのBIT。
オーダーはO(Q log^2Q)。
バグに苦しんで3時間以上かけてしまった。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>bit;
vector<int>damy;
int bitsize;
void init(int a)
{
	bit=damy;
	bitsize=1;
	for(;bitsize<a;bitsize*=2){}
	bitsize++;
	for(int j=0;j<bitsize;j++)
	{
		bit.push_back(0);
	}
}
int sum(int a)
{
	int sumn=0;
	for(;a>0;)
	{
		sumn+=bit[a];
		a-=a&-a;
	}
	return sumn;
}
void add(int a,int b)
{
	for(;a<bitsize;)
	{
		bit[a]+=b;
		a+=a&-a;
	}
}
int main()
{
	for(;;)
	{
		int query,lon;
		scanf("%d%d",&query,&lon);
		if(query==0&&lon==0)
		{
			break;
		}
		init(query);
		vector<pair<int,int> >vec;
		vector<pair<int,int> >bio;
		vector<int>ans;
		for(int i=0;i<query;i++)
		{
			int za,zb;
			scanf("%d%d",&za,&zb);
			vec.push_back(make_pair(za,zb));
			if(za==0)
			{
				bio.push_back(make_pair(zb,-1));
				ans.push_back(zb);
			}
		}
		sort(bio.begin(),bio.end());
		vector<int>map;
		int sta=1,you=0;
		for(int j=0;j<query;j++)
		{
			if(vec[j].first==0)
			{
				int low=lower_bound(bio.begin(),bio.end(),make_pair(vec[j].second,-1))-bio.begin();
				map.push_back(vec[j].second);
				bio[low].second=map.size();
				you++;
				if(you>lon)
				{
					int zan=sta;
					you--;
					int now=sta-sum(sta);
					for(;;)
					{
						sta++;
						if(sta-sum(sta)!=now)
						{
							break;
						}
					}
					add(zan,1);
				}
			}
			if(vec[j].first==3)
			{
				int low=lower_bound(bio.begin(),bio.end(),make_pair(vec[j].second,-1))-bio.begin();
				add(bio[low].second,1);
				you--;
				if(bio[low].second==sta)
				{
					int now=sta-sum(sta);
					for(;;)
					{
						sta++;
						if(sta-sum(sta)!=now)
						{
							break;
						}
					}
				}
			}
			if(vec[j].first==1||vec[j].first==2)
			{
				int han=0;
				if(vec[j].first==1&&vec[j].second==1)
				{
					han=1;
				}
				int beg=1,end=map.size();
				int ban=0;
				int fuga=vec[j].second;
				fuga+=sta-sum(sta)-1;
				for(;;)
				{
					int med=(beg+end)/2;
					if(med-sum(med)<fuga)
					{
						beg=med+1;
					}
					else
					{
						end=med;
					}
					if(end==beg)
					{
						ban=beg;
						break;
					}
				}
				if(vec[j].first==1)
				{
					add(ban,1);
					you--;
					if(han==1)
					{
						int now=sta-sum(sta);
						for(;;)
						{
							sta++;
							if(sta-sum(sta)!=now)
							{
								break;
							}
						}
					}
				}
				else
				{
					printf("%d\n",ans[ban-1]);
				}
			}
		}
		printf("end\n");
	}
}