好久没写线段树都不知道怎么写了。。。

很easy的线段树二分问题

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;#define lson (pos<<1)#define rson (pos<<1|1)const int maxn = 10005;int n,Case = 1;char op[10];int  Hash[maxn];int  cnt;struct In{    int op,v;}in[maxn];int HASH(int x){    return lower_bound(Hash,Hash + cnt,x) - Hash + 1;}int sum[maxn << 2];void pushup(int pos){    sum[pos] = sum[lson] + sum[rson];    return;}void update(int L,int R,int m,int pos,int value){    if(L == R){        sum[pos] = value;        return;    }    int mid = (L + R) >> 1;    if(m <= mid)        update(L,mid,m,lson,value);    else        update(mid + 1,R,m,rson,value);    pushup(pos);    return;}int query(int L,int R,int value,int pos){    if(L == R)        return L;    int mid = (L + R) >> 1;    if(sum[lson] >= value)        return query(L,mid,value,lson);    else        return query(mid + 1,R,value - sum[lson],rson);}int main(){    while(scanf("%d",&n) != EOF){        printf("Case #%d:\n",Case++);        cnt = 0;        queue
          
           q; memset(sum,0,sizeof(sum)); for(int i = 0; i < n; i++){ scanf("%s",op); if(op[0] == 'i'){ in[i].op = 1; scanf("%d",&in[i].v); Hash[cnt++] = in[i].v; } else if(op[0] == 'o') in[i].op = 2; else if(op[0] == 'q') in[i].op = 3; } sort(Hash,Hash + cnt); cnt = unique(Hash,Hash + cnt) - Hash; for(int i = 0; i < n; i++){ if(in[i].op == 1){ int e = HASH(in[i].v); q.push(e); update(1,cnt,e,1,1); } else if(in[i].op == 2){ int e = q.front(); q.pop(); update(1,cnt,e,1,0); } else if(in[i].op == 3){ int f = sum[1]; int fx = f / 2 + 1; int pos = query(1,cnt,fx,1); printf("%d\n",Hash[pos - 1]); } } } return 0;}/*10in 1in 2in 3in 4in 5oqoqq*/