读题读得有点累,不过最后还是看懂了。意思就是给定一组数据按顺序插入,每次在u个元素的时候

(本例中(后略)是1,2,6,6),
找到第i小的数,i= 1,2,3,4...,correspondly,相对应的。

开始用线性表做,TLE了,没注意到查询是线性的……
后来看了参考了别人的solutions,发现了stl中的一个好东东,priority_queue

priority_queue的功能和用法可以看下 C++ STL

至于解题报告嘛,由于我也是参考别人写的代码,所以就不东施效颦了,贴一下:
http://www.stubc.com/thread-3511-1-2.html(这篇分析选用哪个数据结构思路比较好)
http://hi.baidu.com/leisimeng/blog/item/2a307e6110f394d78db10d02.html

P.S. 在代码中间加了一些注释,希望会有一些帮助。


 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int M, N;
 7 int a[30010], u[30010];
 8 
 9 int main() {
10 #ifdef _DEBUG
11     freopen("in.txt""r", stdin);
12     freopen("out.txt""w", stdout);
13 #endif
14     int i, j, value;
15     while (scanf("%d %d"&M, &N) != EOF) {
16         // 左边大根堆,右边小根堆 
17         // 这样,当我们把它们看作一体时,可以保证它的有序性 
18         priority_queue< int, vector<int>, less<int> > hmax;
19         priority_queue< int, vector<int>, greater<int> > hmin;
20         
21         for (i = 0; i < M; i++)
22             scanf("%d"&a[i]);
23 
24         u[0= 0;
25         for (i = 1; i <= N; i++)
26             scanf("%d"&u[i]);
27             
28         for (i = 1; i <= N; i++) {
29             
30             // inserting a+ 0 to 1, 1 to 2, 2 to 6, 6 to 6 according to i
31             for (j = u[i-1]; j < u[i]; j++) {
32                 hmax.push(a[j]);
33                 /* we want to get the i-th smallest number, so when
34                  * we reach i(in the big-root heap), the excessive(for
35                  * ive(for now) must be in the small-root heap so that
36                  * we could sort it and might use it later
37                  */
38                 if (hmax.size() > i-1) {
39                     value = hmax.top();
40                     hmax.pop();
41                     hmin.push(value);
42                 }
43             }
44             // after the loop, the answer is the root of the small-r heap
45             value = hmin.top();
46             hmin.pop();
47             hmax.push(value);
48             printf("%d\n", hmax.top());
49         }
50     }
51 }
52