POJ 1442 Black Box

题意：给定一个集合，有两种操作，插入一个数和查询集合中第i小的数，i每次查询一次前自增1，初始为0.

一开始想先离散化，再用桶来表示这个集合，用树状数组维护查询，后来发现实现起来相当麻烦，而且思路也不够清晰。

一看discuss居然有人用线段树做，简单多了，查询和插入都是O(logn);

复杂度:O(nlogn);

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 30010
using namespace std;

struct ST
{
    int l,r,v;//v保存是的左子树有多少个数
};

ST st[MAXN*4];
int a[MAXN],b[MAXN];

int BSearch(int k,int high)
{
    int low,mid;
    for(low=0;low<=high;)
    {
        mid=(low+high)>>1;
        if(b[mid]==k)
            return mid;
        else if(b[mid]<k)
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}

void BuildST(int l,int r,int i)
{
    st[i].l=l;
    st[i].r=r;
    st[i].v=0;
    int mid=(l+r)>>1;
    if(l<r)
    {
        BuildST(l,mid,i<<1);
        BuildST(mid+1,r,(i<<1)+1);    
    }
}

void Insert(int i,int k)
{
    int mid=(st[i].l+st[i].r)>>1;
    if(k<=mid)
    {
        st[i].v++;
        if(st[i].l<st[i].r)
            Insert(i<<1,k);
    }    
    else
        Insert((i<<1)+1,k);
}

int Query(int i,int j)
{
    if(st[i].l==st[i].r)
        return st[i].l;
    if(j<=st[i].v)
        return Query(i<<1,j);
    return Query((i<<1)+1,j-st[i].v);
        
}

int main()
{
    int i,j,k,t,n,m,l;
    for(;scanf("%d%d",&n,&m)+1;)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",a+i);
            b[i]=a[i];
        }
        sort(b,b+n);
        for(i=j=1;i<n;i++)
            if(b[i]!=b[i-1])
                b[j++]=b[i];
        l=j-1;
        BuildST(0,l,1);
        for(i=j=0;m--;)
        {
            scanf("%d",&t);
            for(;j<t;j++)
            {
                k=BSearch(a[j],l);
                Insert(1,k);
            }
            k=Query(1,++i);
            printf("%d\n",b[k]);    
        }    
    }
    return 0;
}