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级别的简单题)