poj 1442 Black Box

ac了想了好久的题，真心高兴，虽然运行有点慢，但却是用c自己写的堆，代码很短；

思路：维护两个堆，一个小顶堆用于存储所给数列最大的一部分，一个大顶堆用于存储所给数列剩下的最小一部分。

运行过程：

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

当输入1时，我们将3压入存储较大值的小顶堆中，判断存储较小值的大顶堆堆顶为NULL，则直接将3从小顶堆中取出，压入大顶堆，更新两个堆，输出大顶堆堆顶的值。

当输入2时，我们将1压入存储较大值的小顶堆中，判断存储较小值的大顶堆堆顶为不为空，并且小顶堆的堆顶1<3，则我们将1和3互换，从而保证小顶堆始终存储较大的，大顶堆始终存储较小的。因为到了区间尾，跳出循环，将小顶堆的堆顶取出插入大顶堆中，从而保证大顶堆的堆顶就是我们所要求的第n小的值。

输入6时与2相同，只是在循环里多插入小顶堆几个数值。具体见代码：

 1 #include<stdio.h>
 2 #define INF 2000000000 + 1000000
 3 #define MAXN 31000
 4 
 5 int pmax, pmin, m, n, D;
 6 int a[MAXN],amin[MAXN<<1],amax[MAXN<<1],treemax[MAXN<<2],treemin[MAXN<<2];
 7 
 8 void updatemax(int cur)
 9 {
10     for(int i = cur; i^1; i >>= 1)
11     treemax[i>>1] = (amax[treemax[i]]>amax[treemax[i^1]]?treemax[i^1]:treemax[i]);    
12 }
13 
14 void updatemin(int cur)
15 {
16     for(int i = cur; i^1; i >>= 1)
17     treemin[i>>1] = (amin[treemin[i]]>amin[treemin[i^1]]?treemin[i]:treemin[i^1]);
18 }
19 
20 void build()
21 {
22     for(D = 1; D < m + 2; D <<= 1);
23     for(int i = 0; i <= D; i ++){treemax[D+i] = i; treemin[D+i] = i;}
24     for(int i = 0; i <= D; i ++){amax[i] = INF; amin[i] = -INF;}
25 }
26 
27 void init()
28 {
29     while(~scanf("%d%d",&m,&n))
30     {
31         for(int i = 0; i < m; i ++)
32             scanf("%d",&a[i]);
33         build();
34         int u;
35         for(int i = 0, j = 0; i < n; i ++)
36         {
37             scanf("%d",&u);
38             for( ; j < u; j ++)
39             {
40                 amax[pmax++] = a[j];
41                 updatemax(D+pmax-1);
42                 if(amin[treemin[1]] != -INF && amax[treemax[1]] < amin[treemin[1]])
43                 {
44                     int t;
45                     t = amax[treemax[1]];
46                     amax[treemax[1]] = amin[treemin[1]];
47                     amin[treemin[1]] = t;
48                     updatemax(D+treemax[1]);
49                     updatemin(D+treemin[1]);
50                 }
51             }
52             amin[pmin++] = amax[treemax[1]];
53             updatemin(pmin+D-1);
54             amax[treemax[1]] = INF;
55             updatemax(D+treemax[1]);
56             printf("%d\n",amin[treemin[1]]);
57         }
58     }     
59 }
60 
61 int main()
62 {
63     pmax = 1;
64     pmin = 1;
65     init();
66     return 0;
67 }