求區間第k大元素的值，

看代碼的注釋。

#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define M 100001 #define md(x,y) (((x)+(y))>>1) int sorted[M]; struct node{int val[M]; //保存的是當前層的各個位上的數值int num[M]; //記錄比當前元素小的元素的和double sum[M]; //記錄當前元素之前進入左子樹的元素和 }t[20]; //樹的深度void build(int lft,int rht,int p) {if(lft==rht) return;int i,mid=md(lft,rht);int isame=mid-lft+1,same=0;//isame 記錄分到左孩子的個數for(i=lft;i<=rht;i++)if(t[p].val[i]<sorted[mid]) isame--;//先算下等于中間值的有幾個int ln=lft,rn=mid+1;for(i=lft;i<=rht;i++){if(i==lft){t[p].num[i]=0;t[p].sum[i]=0;}else{t[p].num[i]=t[p].num[i-1];t[p].sum[i]=t[p].sum[i-1];} //如果大于，肯定進入右孩子，小于一定進入左孩子。if(t[p].val[i]<sorted[mid]){t[p].num[i]++;t[p].sum[i]+=t[p].val[i];t[p+1].val[ln++]=t[p].val[i];}else if(t[p].val[i]>sorted[mid]){t[p+1].val[rn++]=t[p].val[i];}else{//處理相等的時候的情況if(same<isame){same++;t[p].num[i]++;t[p].sum[i]+=t[p].val[i];t[p+1].val[ln++]=t[p].val[i];}else{t[p+1].val[rn++]=t[p].val[i];}}}build(lft,mid,p+1);build(mid+1,rht,p+1); }double sum=0; int query(int a,int b,int k,int p,int lft,int rht) {if(lft==rht) return t[p].val[a];int s,ss,bb,b2; //s記錄[a,b]進入做孩子的元素個數,ss記錄[lft,a-1)中計入左孩子的元素的個數。sss記錄區間[a,b]中小于第k大元素的和.b2表示[lft,a-1]中分到右孩子的個數,bb表示[a,b]中分到右孩子的個數double sss;int mid=md(lft,rht);if(a==lft){s=t[p].num[b];ss=0;sss=t[p].sum[b];}else{s=t[p].num[b]- t[p].num[a-1];ss=t[p].num[a-1];sss=t[p].sum[b]-t[p].sum[a-1];}if(s>=k){a= lft+ss;b= lft+ss+s-1;return query(a,b,k,p+1,lft,mid);}else{bb=a-lft-ss;b2=b-a-s;a=mid+bb+1;b=mid+1+bb+b2;sum+=sss;return query(a,b,k-s,p+1,mid+1,rht); //在右孩子中} } int main() {int w,i;scanf("%d",&w);while(w--){int n,k;scanf("%d%d",&n,&k);for(i=1;i<=n;i++){scanf("%d",&t[0].val[i]);sorted[i]=t[0].val[i];}sort(sorted+1,sorted+1+n);build(1,n,0);for(i=1;i<=k;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);printf("%d\n",query(a,b,c,0,1,n));}} }

總結

以上是生活随笔為你收集整理的hdu 2665 Kth number 划分树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。