开发学院软件开发C++ 第k元素log(n)算法–划分树 阅读

第k元素log(n)算法–划分树

 2010-11-02 08:53:29 来源:WEB开发网   
核心提示:#include<iostream>#include<cstdio>using namespace std;struct node{ int x,y; };node a[20000]; int d[20][100000],s[20][100000],n,m,x,
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
       int x,y;
       };

node a[20000];      
int d[20][100000],s[20][100000],n,m,x,y,z;
bool cmp(const node a,const node b)
{
     return a.x<b.x;
 }
void buildtree(int h,int l ,int r)
{
     if (l==r) return;
     int mid=(l+r)>>1,p=0;
     for (int i=l;i<=r;++i)
     {
         if (d[h][i]<=mid)
         {
            d[h+1][l+p]=d[h][i];
            ++p;s[h][i]=p;
         } else
         {
            d[h+1][mid+1+i-l-p]=d[h][i];
            s[h][i]=p;
         }
         
     }
     buildtree(h+1,l,mid);
     buildtree(h+1,mid+1,r);
 }
int find(int h,int l,int r,int ll,int rr,int k)
{
    if (ll==rr) return (d[h][ll]);
    int ls=0,rs=0;
    if (ll>l) ls=s[h][ll-1];rs=s[h][rr];
    if (rs-ls>=k) return find(h+1,l,(l+r)>>1,l+ls,l+rs-1,k);
    else return find(h+1,((l+r)>>1)+1,r,((l+r)>>1)+1+ll-l-ls,((l+r)>>1)+rr-l+1-rs,k-(rs-ls));
}
int main()
{
    freopen("350.in","r",stdin);
    freopen("350.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=n;++i)
    {
        cin>>a[i].x;a[i].y=i;
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;++i) d[0][a[i].y]=i;
    buildtree(0,1,n);
    
    for (int i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        cout<<a[find(0,1,n,x,y,z)].x<<endl;
    }
    return 0;
}

直接双击页面元素进行修改的HTML代码

http://tech.cncms.com/sheji/js/66384.html

Tags:元素 log(n) 划分树

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
    赞助商链接