团体程序设计天梯赛
L3-002 特殊堆栈
法三：使用线段树(Segment Tree)。线段树的具体内容，参考：线段树：从没入门到入门
使用数组维护线段树，表示当前数字区间的出现次数和。入栈、出栈所用到的操作是单点修改，时间复杂度是$O(logn)$，求中位数所用到的操作类似于单点查询，时间复杂度是$O(logn)$。
“对已出现的值的范围建树，然后每一次更新就把这个值对应的叶子节点++或–，用cnt记录当前区间内出现了几个数，这样一来查询就好办了，若左子树cnt大于等于k，则肯定在左子树，反之则在右子树，但此时就不是K了，因为k已经大于左子树的cnt了，就是说还剩下k-lson.cnt个数，比如我要查第10大，左边6个右边10个，一共14个数，那肯定就直接从右边开始数10-6个即右边的第4个。”
注：数组需要开4倍叶子节点的大小。
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
vector<int> seg(400010, 0);
void pushup(int pos){
seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
void update(int l, int r, int pos, int tomod, int value){
if(l == r){
seg[pos] += value;
return;
}
int mid = (l + r) / 2;
if(tomod <= mid){ // 左子树
update(l, mid, 2 * pos, tomod, value);
}
else{ // 右子树
update(mid + 1, r, 2 * pos + 1, tomod, value);
}
pushup(pos);
}
void ask(int l, int r, int pos, int toask, int& res){
if(l == r){ // 输出查询结果
res = l;
return;
}
int mid = (l + r) / 2;
if(toask <= seg[2 * pos]){ // 在左子树
ask(l, mid, 2 * pos, toask, res);
}
else{ // 在右子树
ask(mid + 1, r, 2 * pos + 1, toask - seg[2 * pos], res);
}
}
int main(){
int n;
cin >> n;
string op;
int num;
for(int i = 0; i <= n - 1; i++){
cin >> op;
if(op == "Pop"){
if(s.empty()){ cout << "Invalid" << endl; }
else{
num = s.top();
cout << num << endl;
s.pop();
update(1, 100000, 1, num, -1);
}
}
else if(op == "Push"){
cin >> num;
s.push(num);
update(1, 100000, 1, num, 1);
}
else if(op == "PeekMedian"){
if(s.empty()){ cout << "Invalid" << endl; }
else{
int res;
ask(1, 100000, 1, (int)(s.size() + 1) / 2, res);
cout << res << endl;
}
}
}
return 0;
}