hdu 4251 The Famous ICPC Team Again(划分树裸题)

The Famous ICPC Team AgainTime Limit: 30000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 733    Accepted Submission(s): 351


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend#include<algorithm>#include<iostream>#include<string.h>#include<sstream>#include<stdio.h>#include<math.h>#include<vector>#include<string>#include<queue>#include<set>#include<map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=100010;int n,m,md;int seg[20][maxn],lnum[20][maxn],sa[maxn];void init(){ memset(lnum,0,sizeof lnum); sort(sa,sa+n);}void btree(int L,int R,int d){ int i,lm,ls,rs,mid; md=max(d,md); if(L==R) return; mid=(L+R)>>1; lm=mid-L+1; ls=L; rs=mid+1; for(i=L;i<=R;i++) if(seg[d][i]<sa[mid]) lm--; for(i=L;i<=R;i++) { if(i==L) lnum[d][i]=0; else lnum[d][i]=lnum[d][i-1]; if(seg[d][i]==sa[mid]) { if(lm>0) { lnum[d][i]++; seg[d+1][ls++]=seg[d][i]; lm--; } else seg[d+1][rs++]=seg[d][i]; } else if(seg[d][i]<sa[mid]) { lnum[d][i]++; seg[d+1][ls++]=seg[d][i]; } else seg[d+1][rs++]=seg[d][i]; } btree(L,mid,d+1); btree(mid+1,R,d+1);}int qu(int L,int R,int l,int r,int d,int k){ if(L==R) return seg[d][L]; int s,ss,b,bb,mid; if(l==L) ss=0; else ss=lnum[d][l-1];//[1,l-1]进入左树的个数 s=lnum[d][r]-ss;//[l,r]进入左树的个数 //printf("d %d ss %d s %d k %d\n",d,ss,s,k); mid=(L+R)>>1; if(s>=k)//在左树中 return qu(L,mid,L+ss,L+ss+s-1,d+1,k);//注意边界。可以确定L+ss-1不为所求所以从L+ss else { bb=l-L-ss;//[1,l-1]进入右树的个数 b=r-l+1-s;//[l,r]进入右树的个数 return qu(mid+1,R,mid+bb+1,mid+bb+b,d+1,k-s);//mid+1+bb+b-1 }}int main(){ int a,b,i,j,cas=1; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) { scanf("%d",&seg[0][i]); sa[i]=seg[0][i]; } md=0; init(); btree(1,n,0);// for(i=0;i<=md;i++)// {// for(j=1;j<=n;j++)// printf("%d ",seg[i][j]);// printf("\n");// } scanf("%d",&m); printf("Case %d:\n",cas++); while(m--) { scanf("%d%d",&a,&b); printf("%d\n",qu(1,n,a,b,0,(b-a+2)/2)); } } return 0;}