1057 Stack (30分)(树状数组+二分)

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (-th smallest element if N is even, or (-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian

where key is a positive integer no more than 1.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print Invalid instead.

Sample Input:

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

Sample Output:

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

题目分析：开始就觉得不能用遍历来找中间值 想来想去也没找到什么好办法 看了别人的博客 没想到树状数组还能这么用
我认为树状数组只是用来记录前缀和的 但换个思路来想 把元素当作数组下标 出现的次数当作该下标对应的值 
树状数组记录了 对应区间的数的个数 不仅让查找方便 增加元素个数也变得方便了

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <climits>
 3 #include<iostream>
 4 #include<vector>
 5 #include<queue>
 6 #include<map>
 7 #include<set>
 8 #include<stack>
 9 #include<algorithm>
10 #include<string>
11 #include<cmath>
12 using namespace std;
13 const int maxn = 100010;
14 int C[100010];
15 stack<int> S;
16 int lowbit(int num)
17 {
18     return num & (-num);
19 }
20 int getSum(int x)
21 {
22     int sum = 0;
23     while (x)
24     {
25         sum += C[x];
26         x -= lowbit(x);
27     }
28     return sum;
29 }
30 void Update(int x, int value)
31 {
32     while (x<maxn)
33     {
34         C[x] += value;
35         x += lowbit(x);
36     }
37 }
38 void PeekMedian()
39 {
40     int left = 1, right = maxn;
41     int k = (S.size() + 1) / 2;
42     while (left<right)
43     {
44         int mid = (left + right) / 2;
45         if (getSum(mid)>= k)
46             right = mid;
47         else
48             left = mid+1;
49     }
50     cout <<left<< endl;
51 }
52 int main()
53 {
54     int N;
55     cin >> N;
56     for (int i = 0; i < N; i++)
57     {
58         string s;
59         cin >> s;
60         if (s == "Push")
61         {
62             int i;
63             cin >> i;
64             S.push(i);
65             Update(i, 1);
66         }
67         else if (s == "Pop")
68         {
69             if (!S.size())
70                 cout << "Invalid" << endl;
71             else
72             {
73                 Update(S.top(), -1);
74                 cout << S.top()<<endl;
75                 S.pop();
76             }
77         }
78         else {
79             if (!S.size())
80                 cout << "Invalid" << endl;
81             else
82                 PeekMedian();
83         }
84     }
85 }

View Code