团体程序设计天梯赛 L3-002 特殊堆栈 (30分)（树状数组+二分）

题目链接：

L3-002 特殊堆栈 (30分)

思路：

用stack容器模拟栈的入栈和出栈；
用树状数组bit[i]维护前缀和；
查找中值时二分树状数组的sum()即可；

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
int n, bit[maxn];
inline void add(int i, int x) { while(i < maxn) bit[i] += x, i += i & -i; }
inline int sum(int i) {
	int res = 0;
	while(i) res += bit[i], i -= i & -i;
	return res;	
}
int get(int num) {
	int l = 1, r = 1e5, res;
	while(l <= r) {
		int mid = (l + r) >> 1, now = sum(mid);
		if(now < num) l = mid + 1;
		else res = mid, r = mid - 1;
	}
	return res;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	cin >> n;
	stack<int> st;
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if(s == "Push") { int x; cin >> x; add(x, 1); st.push(x); }
		else if(st.empty()) { cout << "Invalid
"; }
		else if(s == "Pop") { cout << st.top() << '
'; add(st.top(), -1); st.pop(); }
		else cout << get((st.size() + (st.size() & 1)) >> 1) << '
';
	}
	return 0;
}