CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
/*
归并树, 求区间[c, d]中第k小的数。 
*/

#include 
<iostream>
using namespace std;
#define MAX_SIZE 100010
struct Tree//线段树结构体 
{
    
int l, r, bit;
}tree[
3 * MAX_SIZE];

int hash[22][MAX_SIZE];

void MakeTree(int k, int bit, int l, int r)
//建立线段树,同时记录归并排序过程 
{
     tree[k].bit 
= bit;
     tree[k].l 
= l, tree[k].r = r;
     
if (l == r)
     {
         hash[bit][l] 
= hash[0][l];
         
return ;
     }
     
int low = (l + r) >> 1;
     MakeTree(k 
<< 1, bit + 1, l, low);
     MakeTree((k 
<< 1+ 1, bit + 1, low + 1, r);
     
     
int inf = l, i = l, j = low + 1;
     
while (i <= low && j <= r)
     {
          
if (hash[bit + 1][i] < hash[bit + 1][j])
             hash[bit][inf
++= hash[bit + 1][i++];
          
else
             hash[bit][inf
++= hash[bit + 1][j++];
     }
     
while (i <= low)hash[bit][inf++= hash[bit + 1][i++];
     
while (j <= r)hash[bit][inf++= hash[bit + 1][j++];
}

int find(int k, int x)
//查找x在区间[tree[k].l, tree[k].r],比x小的个数 
{
    
int l = tree[k].l, r = tree[k].r, bit = tree[k].bit;
    
int mid;
    
while (l <= r)
    {
         mid 
= (l + r) >> 1;
         
if (hash[bit][mid] < x)
         {
             l 
= mid + 1;
         }
         
else
            r 
= mid - 1;
    }
    
return l - tree[k].l;
}

int rank(int k, int x, int l, int r)
//查找在区间[l, r]中比x小的个数 
{
      
if (l == tree[k].l && r == tree[k].r)
      {
          
return find(k, x);
      }
      
int low = (tree[k].l + tree[k].r) >> 1;
      
int c1 = 0, c2 = 0;
      
if (r <= low)
      c1 
= rank(2 * k, x, l, r);
      
else if (l > low)
      {
           c2 
= rank(2 * k + 1, x, l, r);
      }
      
else
      {
          c1 
= rank(2 * k, x, l, low);
          c2 
= rank(2 * k + 1, x, low + 1, r);
      }
      
return c1 + c2;
}

bool check(int x, int l, int r, int k)
{
     
int rs = rank(1, x, l, r);
     
return rs < k;
}
int main()
{
    
int i, s, p, k, n, t, m, l, r, mid;
    
while (scanf("%d%d"&n, &m) != EOF)
    {
        
        
for (i = 1; i <= n; i++)
        {
           scanf(
"%d"&hash[0][i]);
        }
        MakeTree(
101, n);
        
for (i = 0; i < m; i++)
        {
            scanf(
"%d%d%d"&s, &p, &k);
            
if (s > p)
            {
               t 
= s;
               s 
= p;
               p 
= t;
            }
            
int re = 1;
            l 
= 1, r = n;
          
            
while (l <= r)
            {
                 mid 
= (l + r) >> 1;
                 
if (check(hash[0][mid], s, p, k))
                 {
                      re 
= mid;
                      l 
= mid + 1;
                 }
                 
else r = mid - 1;
            }
            printf(
"%d\n", hash[0][re]);
        }
    }
    
return 0;
}
posted on 2011-04-11 21:04 CodeStream 阅读(407) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理