hdu 4417 划分树加二分 求区间内小于num的数的个数

Super MarioTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 771    Accepted Submission(s): 423


Problem DescriptionInputOutputSample InputSample OutputSource#include<stdio.h> #include<algorithm> using namespace std; #define M 100005 int tree[40][M],sorted[M]; int toLeft[40][M]; void build(int level,int left,int right){ if(left==right)return ; int mid=(left+right)>>1; int i; int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid] suppose=mid-left+1; for(i=left;i<=right;i++){ if(tree[level][i]<sorted[mid]){ suppose--; } } //如果suppose==1，则说明数组中值为sorted[mid]只有一个数。比如序列：1 3 4 5 6，sorted[mid]=4 /*如果suppose>1，则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。比如序列：1 4 4 4 6，sorted[mid]=4 */ int lpos=left,rpos=mid+1; for(i=left;i<=right;i++){ if(i==left){//这里是预处理，相当与初始化 toLeft[level][i]=0; }else{ toLeft[level][i]=toLeft[level][i-1]; } if(tree[level][i]<sorted[mid]){//划分到中位数左边 toLeft[level][i]++; tree[level+1][lpos++]=tree[level][i]; }else if(tree[level][i]>sorted[mid]){//划分到中位数右边 tree[level+1][rpos++]=tree[level][i]; }else{//这里，suppose大于0的数划分到中位数的左边 if(suppose!=0){//这里的处理太巧妙了！帅气！ suppose--; toLeft[level][i]++; tree[level+1][lpos++]=tree[level][i]; }else{//表示 tree[level+1][rpos++]=tree[level][i]; } } } build(level+1,left,mid); build(level+1,mid+1,right); } //在[left,right]数据中查询[qleft,qright]中第k大的数据 int query(int level,int left,int right,int qleft,int qright,int k){ if( qleft==qright) return tree[level][qleft]; int s;//代表[left,qleft)之间有多个个元素被分到左边 int ss;//[qleft, qright]内将被划分到左子树的元素数目 int mid=(left+right)>>1; if(left==qleft){ s=0; ss=toLeft[level][qright];}else{ s=toLeft[level][qleft-1]; ss=toLeft[level][qright]-s; } int newl,newr; if(k<=ss){//查询左边 newl=left+s; newr=left+s+ss-1; return query(level+1,left,mid,newl,newr,k); }else{//查询右边 newl=mid-left+1+qleft-s; newr=mid-left+1+qright-s-ss; return query(level+1,mid+1,right,newl, newr,k - ss); } } int main(){ int n,m,cas,ca=0;scanf("%d",&cas);while(cas--){printf("Case %d:\n",++ca); scanf("%d %d",&n,&m); int i; for(i=1;i<=n;i++){ scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(0,1,n); int ql,qr,num,ans=0; for(i=0;i<m;i++){ scanf("%d %d %d",&ql,&qr,&num);ql++;qr++;//注意这里哦 题意是按从0开始的 int mid,left=1,right=qr-ql+1,ans=0;mid=(left+right)/2;while(left<=right)//别少了等于号{mid=(left+right)/2; if(query(0,1,n,ql,qr,mid)>num) right=mid-1;else {ans=mid;left=mid+1;}//我一开始写的二分法居然不知道是哪里出错了一个劲RE}printf("%d\n",ans);} } return 0; }