hdu 2665 Kth number 划分树

求区间第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 划分树,布布扣,bubuko.com

hdu 2665 Kth number 划分树

原文：http://blog.csdn.net/cnh294141800/article/details/20653801