学到一个很强的数据结构，其实就是线段树+归并排序，把归并排序的每个阶段保存下来，然后就可以像线段树那样查询了。
可以快速查询一个序列中某一段x是第几大的、某一段第k大的数
因为每条线段都是有序的，所以可以二分查找一个数在这条线段上的rank值，利用线段树把查询的线段分成几个子线段，那么总的rank值就是这些子线段rank值的和。查询第k大的数再二分答案一下，一共3次二分（算上线段树），查询一次的时间为O(log(n)^3)
poj2104:
1 #include<cstdio>
2
3 #define N 100000
4 int n,max=-0x7fffffff,min=0x7fffffff;
5 int a[N],tree[18][N];
6 struct Node
7 {
8 int depth,left,right;
9 }node[1<<19];
10
11 void MergeSort(int p,int depth,int l,int r)
12 {
13 node[p].depth=depth; node[p].left=l; node[p].right=r;
14 if(l+1==r) tree[depth][l]=a[l];
15 else
16 {
17 int mid=(l+r)>>1;
18 MergeSort(p<<1,depth+1,l,mid);
19 MergeSort((p<<1)+1,depth+1,mid,r);
20 int p1=l,p2=mid;
21 while(l<r)
22 {
23 if(p1==mid)
24 tree[depth][l++]=tree[depth+1][p2++];
25 else if(p2==r)
26 tree[depth][l++]=tree[depth+1][p1++];
27 else
28 {
29 if(tree[depth+1][p1]<tree[depth+1][p2])
30 tree[depth][l++]=tree[depth+1][p1++];
31 else
32 tree[depth][l++]=tree[depth+1][p2++];
33 }
34 }
35 }
36 }
37
38 void init()
39 {
40 for(int i=0;i<n;i++)
41 {
42 scanf("%d",&a[i]);
43 if(a[i]>max) max=a[i];
44 if(a[i]<min) min=a[i];
45 }
46 MergeSort(1,0,0,n);
47 }
48
49 int Rank(int p,int l,int r,int x)
50 {
51 if(r<node[p].left || l>node[p].right) return 0;
52 if(l<node[p].left) l=node[p].left;
53 if(r>node[p].right) r=node[p].right;
54 if(l==node[p].left && r==node[p].right)
55 {
56 r--;
57 int depth=node[p].depth;
58 if(x<=tree[depth][l]) return 0;
59 if(x>tree[depth][r]) return r-l+1;
60 while(l+1<r)
61 {
62 int mid=(l+r)>>1;
63 if(tree[depth][mid]<x) l=mid;
64 else r=mid;
65 }
66 return l-node[p].left+1;
67 }
68 return Rank(p<<1,l,r,x)+Rank((p<<1)+1,l,r,x);
69 }
70
71 int Query(int i,int j,int k)
72 {
73 int l=min,r=max+1;
74 while(l+1<r)
75 {
76 int mid=(l+r)>>1;
77 if(Rank(1,i,j,mid)+1>k) r=mid;
78 else l=mid;
79 }
80 return l;
81 }
82
83 int main()
84 {
85 int q,i,j,k;
86 scanf("%d%d",&n,&q);
87 init();
88 while(q--)
89 {
90 scanf("%d%d%d",&i,&j,&k);
91 printf("%d\n",Query(i-1,j,k));
92 }
93 return 0;
94 }
95
|
|
