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; } }