POJ P2104 K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

（主席树求区间第k小）

——by POJ；

http://poj.org/problem?id=2104

先%hjt吧；

主席树静态求区间第K小；

先对数据按大小离散化；

然后明确两个概念：

排名区间：排名区间[l,r]表示要维护排名在lr间的数据的相关信息；
原序列区间：原序列区间[x,y]表示要维护在原序列（至把数据按读入的顺序排列的序列）中xy间的数据的相关信息；

我们对原序列中的每一个点，维护她的前缀信息——

信息是：一棵线段树——以排名区间为区间，维护有多少数据在该区间里（如原序列：3,3,2,1,3,则第3位的前缀是{3,3,2}，于是维护{3,3,2}中有几个在排名区间[1,3]中，有几个在排名区间[1,2]，有几个在排名区间[3,3]...）；

这样你得到了如下信息：

原序列区间[1,j]中数据在排名区间中的分布（因为你记录了前缀影响下的线段树嘛）；
利用上一条信息得出：原序列区间[i,j]中数据在排名区间中的分布（对前缀进行差分）;

在我们有原序列区间[i,j]中数据在排名区间中的分布信息后，

　　若排名区间[l,mid]中分布k+个数据，则区间[l,r]的第k小必然在该区间里；

　　否则在排名区间[mid+1,r]中；

　　然后在线段树上递归分治即可；

以上是中心思路——

然后，是一些要点：

　　如，如何N棵线段树的内存问题？

　　　　其实，表面上看我们要开N棵树，但是相邻两树只有受一个数据影响而产生的差距——这只会造成一条树链的不同；

　　这样只存一棵树和N-1条链即可；

　　习惯上我们一般以完全二叉树的方式存储，在这里是不行的；

　　用最朴素的二叉树存储方法，即对一个点，维护她所代表的区间的信息和左右子节点的下标信息即可；

　　然后可以考虑内存池模拟系统内存分配的方法（我一开始还以为是内存尺的说）；

（终于把这篇拖了许久的东西发上来了，大概是我写的最长的随笔了吧；）

代码如下：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct ss
 5 {
 6     int size,num;
 7 }a[100001];
 8 int b[100001],fa[100001],L,R,K,now;
 9 struct tre
10 {
11     int l,r,num;
12 }tr_data[2000000];
13 int tot;
14 
15 bool cmp1(ss a,ss b)
16 {    return a.size<b.size;    }
17 
18 bool cmp2(ss a,ss b)
19 {    return a.num<b.num;        }
20 void build(int ,int ,int ,int );
21 void work(int ,int ,int ,int );
22 
23 int main()
24 {
25     int i,j=0,k;
26     int n,m;
27     scanf("%d%d",&n,&m);
28     for(i=1;i<=n;i++)
29         scanf("%d",&a[i].size),a[i].num=i;
30     
31     sort(a+1,a+n+1,cmp1);
32     for(i=1;i<=n;i++)
33     {
34         if(a[i].size!=a[i-1].size)++j;
35         b[j]=a[i].size;
36         a[i].size=j;
37         
38     }
39     sort(a+1,a+n+1,cmp2);
40 
41     for(i=1;i<=n;i++)
42     {
43         fa[i]=++tot;
44         now=a[i].size;
45         build(1,j,tot,fa[i-1]);//////
46     }
47     for(i=1;i<=m;i++)
48     {
49         scanf("%d%d%d",&L,&R,&K);
50         work(1,j,fa[R],fa[L-1]);//////
51     }
52     return 0;
53 }
54 
55 void build(int l,int r,int nu,int pre)
56 {
57     if(l==r)
58     {
59         tr_data[nu].num=tr_data[pre].num+1;
60         return;
61     }
62     int mid=(l+r)>>1;
63     if(now<=mid)
64     {
65         tr_data[nu].l=++tot;
66         build(l,mid,tr_data[nu].l,tr_data[pre].l);
67         tr_data[nu].r=tr_data[pre].r;
68     }
69     else
70     {
71         tr_data[nu].r=++tot;
72         build(mid+1,r,tr_data[nu].r,tr_data[pre].r);
73         tr_data[nu].l=tr_data[pre].l;
74     }
75     tr_data[nu].num=tr_data[tr_data[nu].l].num+tr_data[tr_data[nu].r].num;
76 }
77 
78 void work(int l,int r,int now,int pre)
79 {
80     if(l==r)
81     {
82         printf("%d
",b[l]);
83         return ;
84     }
85     int mid=(l+r)>>1;
86     if(tr_data[tr_data[now].l].num-tr_data[tr_data[pre].l].num>=K)
87         work(l,mid,tr_data[now].l,tr_data[pre].l);
88     else
89         {    K=K-(tr_data[tr_data[now].l].num-tr_data[tr_data[pre].l].num);
90             work(mid+1,r,tr_data[now].r,tr_data[pre].r);    }
91 }

祝AC哟；

POJ P2104 K-th Number

相关推荐