团体程序设计天梯赛
L3-002 特殊堆栈
法二：使用树状数组。所维护的数组是当前数字的出现次数组成的数组。入栈、出栈所用到的操作是单点修改，时间复杂度是$O(logn)$，求中位数所用到的操作是二分法+区间查询(求和)，时间复杂度是$O(log^2n)$。
#include <bits/stdc++.h>
using namespace std;
vector<int> bitArr(100001); // how many cnts that equal the num given
stack<int> s;
int lowbit(int x){ return x&(-x); }
void add(int x, int v){
for(; x <= 100000; x += lowbit(x)) bitArr[x] += v;
}
int ask(int x){
int sum = 0;
for(; x >= 1; x -= lowbit(x)) sum += bitArr[x];
return sum;
}
int main(){
int n;
cin >> n;
string op;
for(int i = 0; i <= n - 1; i++){
cin >> op;
if(op == "Pop"){
if(s.empty()) cout << "Invalid" << endl;
else{
int value = s.top();
cout << value << endl;
s.pop();
add(value, -1);
}
}
else if(op == "Push"){
int value;
cin >> value;
s.push(value);
add(value, 1);
}
else if(op == "PeekMedian"){
if(s.empty()) cout << "Invalid" << endl;
else{
int k = ((int)s.size() + 1) / 2;
int l = 1, r = 100001;
while(l < r){
if(ask((l + r) / 2) < k) l = (l + r) / 2 + 1;
else if (ask((l + r) / 2) >= k) r = (l + r) / 2;
} // final: l == k
cout << l << endl;
}
}
}
return 0;
}