你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
const int maxn = 1e5+5;
int op[maxn];
int a[maxn];
int tree[maxn<<2];
vector<int>vc;
void push_up(int rt)
{
tree[rt] = tree[lson]+tree[rson];
}
void build(int rt,int l,int r)
{
if(l==r)
{
tree[rt] = 0;
return;
}
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(rt);
}
void update(int rt,int l,int r,int pos,int tmp)
{
if(l==r)
{
tree[rt]+=tmp;
return ;
}
int mid = (l+r)>>1;
if(pos<=mid) update(lson,l,mid,pos,tmp);
else update(rson,mid+1,r,pos,tmp);
push_up(rt);
}
int query(int rt,int l,int r,int pos)
{
if(l==r)return l;
int mid = (l+r)>>1;
if(tree[lson]>=pos)return query(lson,l,mid,pos);
else return query(rson,mid+1,r,pos-tree[lson]);
}
int main()
{
int n;
int cases = 0;
while(cin>>n)
{
printf("Case #%d:\n",++cases);
char tmp[10];
queue<int>o;
vc.clear();
for(int i=1; i<=n; i++)
{
scanf("%s",tmp);
if(tmp[0]=='i')
{
scanf("%d",&op[i]);
vc.emplace_back(op[i]);
}
else if(tmp[0]=='o')
op[i] = -1;
else op[i] = -2;
}
sort(vc.begin(),vc.end());
int nn =unique(vc.begin(),vc.end())-vc.begin();
build(1,1,nn);
for(int i=1; i<=n; i++)
{
if(op[i]>=0)
{
int k = lower_bound(vc.begin(),vc.end(),op[i])-vc.begin()+1;
o.push(op[i]);
update(1,1,nn,k,1);
}
else if(op[i]==-1)
{
int k = lower_bound(vc.begin(),vc.end(),o.front())-vc.begin()+1;
update(1,1,nn,k,-1);
o.pop();
}
else
{
int k =query(1,1,nn,o.size()/2+1);
printf("%d\n",vc[k-1]);
}
}
}
return 0;
}
京公网安备 11010502036488号