hdu 2665 划分树

对划分树的详解昂上已经很清楚了  ，    这就是道裸划分树题    ，敲吧！！！！！；

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int tree[20][100010];
int sum[20][100010],num[100010];
int build(int floot,int L,int R)
{
    int i;
    int mid=(R+L)/2;
    int cont=mid-L+1;
    int lstar=L,rstar=mid+1;
    for(i=L;i<=mid;i++)
    {
        if(num[i]<num[mid]) cont--;    
    }
    for(i=L;i<=R;i++)
    {
        if(i==L) sum[floot][i]=0;
        else sum[floot][i]=sum[floot][i-1];
        if(tree[floot][i]==num[mid])
        {
            if(cont)
            {
                cont--;
                sum[floot][i]++;
                tree[floot+1][lstar++]=tree[floot][i];
            }
            else
            {
                tree[floot+1][rstar++]=tree[floot][i];
            }
        }
        else if(tree[floot][i]<num[mid])
        {
            sum[floot][i]++;
            tree[floot+1][lstar++]=tree[floot][i];
        }
        else
        {
            tree[floot+1][rstar++]=tree[floot][i];
        }
        
    }
    
    if(L==R) return 0; 
    build(floot+1,L,mid);
    build(floot+1,mid+1,R);
    return 0;
}
int find(int floot,int L,int R,int left,int right,int k)
{
    if(L==R) return tree[floot][L];
    int mid=(L+R)/2;
    int sum1,sum2;
    if(L==left)
    {
        sum1=0;
        sum2=sum[floot][right];
    }
    else
    {
        sum1=sum[floot][left-1];
        sum2=sum[floot][right]-sum1;
    }
    if(k<=sum2) return find(floot+1,L,mid,L+sum1,L+sum1+sum2-1,k);
    return find(floot + 1, mid + 1, R, mid - L + 1 + left - sum1, mid - L + 1 + right - sum1 - sum2,k - sum2);            
}
int main()
{
    int n,m,i,j,T,k,left,right;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            tree[1][i]=num[i];
        }
        sort(num+1,num+1+n);
        build(1,1,n);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&left,&right,&k);
            printf("%d\n",find(1,1,n,left,right,k));
        }
    }
    return 0;
}

hdu 2665 划分树

原文：http://blog.csdn.net/zxf654073270/article/details/44623981