Solve

POJ2104归并树

题目解答

使用线段树的划分结构维护归并排序，线段树是虚的，不需要建立出来。查找时，大体分为三次：首先二分总区间的中值 -> 接着使用已经建好的归并树二分中值在待查区间的排位(需要两个小的二分组成) -> 若与待查排位一致就输出，否则总区间折半继续上述步骤直到找到。

本题目实现以后，我从一个神人的Blog发现了使用 STL 优化的方法：查待查区间的排位可以用STL。(冬令营上说可以使用)

我原本的程序：长61Lines | 运行时间::3.4s;
使用STL后的程序：长56Lines | 运行时间::2.4s; <– OTL

运行情况

POJ2104归并树

POJ2104归并树

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>    // 优化了一下代码 
#define MAX 100001 //确定区间上界
#define BIG 19     //确定归并树深度 

long seg[BIG][MAX],val[MAX],m,n,x,y,rank; //seg,val分别存储归并树 ,原数列.
struct Node{                              // 存储线段树的分割 
    long left,right,mid;
}tr[2*MAX+MAX/2];
void build(long index,long l,long r,long deep){ //建立归并树
     tr[index].left=l;
    tr[index].right=r;
    tr[index].mid=(l+r)>>1;
    if(l==r){
        seg[deep][l]=val[l];
        return ;
    }
    build(index<<1,l,tr[index].mid,deep+1);
    build((index<<1)+1,tr[index].mid+1,r,deep+1);
    long mid=(l+r)>>1,ln=l,rn=mid+1,pos=l;
    while(ln<=mid && rn<=r){
        if(seg[deep+1][ln]>seg[deep+1][rn])
            seg[deep][pos++]=seg[deep+1][rn++];
        else seg[deep][pos++]=seg[deep+1][ln++];
    }
    if(ln==mid+1) while(rn<=r) seg[deep][pos++]=seg[deep+1][rn++];
    else while(ln<=mid) seg[deep][pos++]=seg[deep+1][ln++];
}
long bigger(long index,long find,long deep){ //返回一个严格排名 (比多少个数大)
    if(tr[index].left==tr[index].right){
        if(find>seg[deep][tr[index].mid]) return tr[index].mid+1;
        else return tr[index].mid;}
    if(find<=seg[deep][tr[index].mid]) return bigger(index<<1,find,deep);
    if(find>seg[deep][tr[index].mid]) return bigger((index<<1)+1,find,deep);
}
long Rank(long index,long find,long deep){   //二分排名 
    if(x<=tr[index].left && tr[index].right<=y)
        return bigger(index,find,deep)-tr[index].left;
    long Find=0;
    if(x<=tr[index].mid) Find+=Rank(index<<1,find,deep+1);
    if(y>tr[index].mid) Find+=Rank((index<<1)+1,find,deep+1);
    return Find;
}
inline long query(){                        // 二分总区间 
    long left=1,right=n,mid,rend;
    while(left<right){
        mid=(left+right+1)>>1;
        rend=Rank(1,seg[1][mid],1);
        if(rend<rank) left=mid;
        else right=mid-1;
    }
    return left;
}
int main(){
    scanf("%ld%ld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%ld",&val[i]);
    build(1,1,n,1);
    while(m--){
        scanf("%ld%ld%ld",&x,&y,&rank);
        printf("%ld\n",seg[1][query()]);
    }
    return 0;
}

ADVENTop吐槽

  1. 谁能告诉我什么是吐槽?
  2. 从小U牛那里第一次看见本题，从Lilymona牛那里了解了归并树，这也是一道流行题吗?
  3. 一开始我不知怎么着一高兴把程序粘贴到回收站里去了，然后立即条件反射 -> 右键 -> 清空回收站 -> 然后我就囧了
  4. Windows太Bug了，回收站还能粘贴!!!(>-<)
  5. STL很厉害呀!

难易等级

Middle Up(NOI级别的简单题)