HDU ACM 5249 KPI->ツリー配列+二分
解析:キューに保存されているのは、ソート後の配列の下付き文字であることに注意してください.ツリー配列も下付き文字で処理されます.
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define N 10005
int c[N<<2];
int n,a[N],b[N];
char str[N][10];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
while(x<N)
{
c[x]+=val;
x+=lowbit(x);
}
}
int sum(int x)
{
int s=0;
while(x>0)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
int solve(int x)
{
int id,l,r,mid;
id=x/2+1;
l=1;
r=N;
while(l<=r)
{
mid=(l+r)>>1;
if(sum(mid)>=id)
r=mid-1;
else
l=mid+1;
}
return b[l];
}
int main()
{
int x,T=0,i,cnt;
while(scanf("%d",&n)==1)
{
queue<int> q;
memset(c,0,sizeof(c));
cnt=1;
for(i=1;i<=n;i++)
{
scanf("%s",str[i]);
if(str[i][0]=='i')
{
scanf("%d",&x);
b[cnt++]=x;
a[i]=x;
}
}
sort(b+1,b+cnt+1); //
cnt=unique(b+1,b+cnt+1)-(b+1); //
printf("Case #%d:
",++T);
for(i=1;i<=n;i++)
{
if(str[i][0]=='i')
{
x=lower_bound(b+1,b+cnt+1,a[i])-b;
update(x,1);
q.push(x); //
}
else if(str[i][0]=='o')
{
x=lower_bound(b+1,b+cnt+1,b[q.front()])-b;
update(x,-1);
q.pop();
}
else if(str[i][0]=='q')
printf("%d
",solve(q.size()));
}
}
return 0;
}