CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
/*
划分树,求解给定区间[l, r]的第k小。
和归并是相反,相当于把归并树倒过来。
当访问到节点t时,sum[bit][i](left <= i <= right)表示从第left个数到第i个数中
有sum[bit][i]个数进入了左子树。
假如我们在区间[left, right]中求解[l, r]中的第k小的时候(left <= l <= r <= right),
看在区间[l,r]中有多少个数进入了左子树,如果有s个,如果s>=k,则递归到左节点,但是
要注意的是,当访问的左节点的时候,求解的区间[l, r]要发生变化 ,即找到区间[l, r]中
第一次出现在左子树的位置ll,和最后一次出现在左子树的位置rr,然后访问左子树的区间
[ll, rr],一直到left=right,返回元数列sa[left]为所求。 

*/


#include 
<iostream>
#include 
<algorithm>
using namespace std;
#define MAX_SIZE 100010

struct Tree
{
    
int l, r, bit;
}tree[
3 * MAX_SIZE];

int sum[24][MAX_SIZE]; //记录划分过程的数组,需要空间为n*logn 
int a[2][MAX_SIZE];   // 滚动数组, 在划分过程中,保存上一层的序列,最开始时将
                     
//将数组存放到a[0][i]中 
int sa[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)
        
return ;
     
int inf = (bit & 1);
     
int low = (l + r) >> 1;
     
int temp = 0;
     
int t = 0;
     
int c = 0;
     
while (low - temp >= l && sa[low - temp] == sa[low])temp++;
     
int i = l, j = low + 1;
     
for (;l <= r; l++)
     {
         
if (a[inf][l] < sa[low])
         {
             c
++;
             sum[bit][l] 
= c;
             a[
1 - inf][i++= a[inf][l];
         }
         
else if (a[inf][l] == sa[low] && t < temp)
         {
             c
++;
             sum[bit][l] 
= c;
             a[
1 - inf][i++= a[inf][l];
             t
++;
         }
         
else 
         {
              sum[bit][l] 
= c;
              a[
1 - inf][j++= a[inf][l];
         }
     }
     l 
= tree[k].l;
     MakeTree(
2 * k, bit + 1, l, low);
     MakeTree(
2 * k + 1, bit + 1, low + 1, r);
}

int Find_rank(int k, int l, int r, int t)
{
    
int bit = tree[k].bit;
    
int left = tree[k].l, right = tree[k].r;
    
int low = (left + right) >> 1;
    
if (right == left)
    {
      
return sa[left];
    }
    
int s;
    
if (l == left)
       s 
= sum[bit][r];
    
else
       s 
= sum[bit][r] - sum[bit][l - 1];
    
if (s >= t)
    {
       
if (l == left)
       
return Find_rank(2 * k, left, left + sum[bit][r] - 1, t);
       
else
       
return Find_rank(2 * k, left + sum[bit][l - 1], left + sum[bit][r] - 1, t);
    }
    
else
    {
        
if (l == left)
        
return Find_rank(2 * k + 1, low + 1, low + 1 + r - l - s, t - s);
        
else
        
return Find_rank(2 * k + 1, low + 1 + l - left - sum[bit][l - 1], low + r - left + 1 - sum[bit][r], t - s);
    }
}

int main()
{
    
int i, j, k, l, m, n, t, r;
    
while (scanf("%d%d"&n, &m) != EOF)
    {
          
          memset(sum, 
0sizeof(sum));
          
for (i = 1; i <= n; i++)
          {
              scanf(
"%d"&a[0][i]);
              sa[i] 
= a[0][i];
          }
          sort(sa 
+ 1, sa + n + 1);
          MakeTree(
101, n);
          
          
for (i = 0; i < m; i++)
          {
              scanf(
"%d%d%d"&l, &r, &k);
              printf(
"%d\n", Find_rank(1, l, r, k));
          }
    }
    
return 0;
}

posted on 2011-04-11 21:10 CodeStream 阅读(661) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理