PKU 1785 Binary Search Heap Construction

http://poj.org/problem?id=1785
文字列と数字のペアが与えられるので、それを使ってtreapを構築しろというような問題。

区間木とかをはじめて蟻本みないで実装しました。
1ヶ月くらいまえに問題の解釈を間違えていたまま、WAとかTLEとかをしまくっていた問題だったので、決着がつけれてよかったです。

int interval[1000000];
pair<string,int> inl[51000];
int _n,n;

void insert(int pos){
  int upos=pos+_n;
  interval[upos]=pos;
  while(upos>0){
    upos=(upos-1)/2;
    if(inl[pos].S>=inl[interval[upos]].S)
      interval[upos]=pos;
  }
}

int query(int l,int u,int cl,int cu,int k){
  if(u<=cl || cu<=l)return n;
  if(cl<=l && u<=cu)return interval[k];
  int v1=query(l,(l+u)/2,cl,cu,k*2+1);
  int v2=query((l+u)/2,u,cl,cu,k*2+2);
  if(inl[v1].S>inl[v2].S)return v1;
  else return v2;
}

void dfs(int l,int u){
  cout<<'(';
  int v=query(0,_n+1,l,u,0);
  if(l<v)dfs(l,v);
  cout<<inl[v].F<<'/'<<inl[v].S;
  if(v+1<u)dfs(v+1,u);
  cout<<')';
}

main(){
  ios::sync_with_stdio(false);
  while(cin>>n,n){
    memset(interval,0,sizeof(interval));

    _n=1;
    while(_n<=n*2)_n=_n*2;
    --_n;
    rep(i,_n*2)interval[i]=n;
    inl[n].S=-1;

    string str;
    rep(i,n){
      int num=0;
      cin>>str;
      num=0;
      int pos=0;
      for(;;pos++){
        if(str[pos]=='/')break;
      }
      inl[i].F=str.substr(0,pos);      
      ++pos;
      for(;pos<str.size();)num=num*10+str[pos++]-'0';
      inl[i].S=num;
    }
    sort(inl,inl+n);
    rep(i,n)insert(i);
    dfs(0,n);
    cout<<endl;
  }
}