树状数组+模拟堆栈

树状数组重要应用之：在n个数字中z找到第k大的数字（树状数组+二分）O(logn^2)

一开始只使用的模拟堆栈做的，但是执行去中值的命令时，我是用sort做的这必然会超时，但是这样可以得到第一个和倒数第一个测试点的分值，接下来就要考虑如何优化了，正好看到网上一个大哥用树状数组做的，特地去学习了一下这个数据结构

最后实现了时间复杂度为O(nlog^2)的算法，通过所有的测试点

#include <bits/stdc++.h>
#include <string.h>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<string,string> PII;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
const int M=1e5+10;
int s,en;
int n,m,k,maxd;
int head[N],e[M],ne[M],tot;
bool st[N];
int tr[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    for(int i=x;i<=N;i+=lowbit(i)){
        tr[i]+=c;
    }
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
int main(){
    string str;
    int tt=0;
    int q[N];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>str;
        if(str.size()==3){
            if(!tt) puts("Invalid");
            else {
                int x=q[--tt];
                cout<<x<<endl;
                add(x,-1); // 去除数字x表示目前可以取的数字中x的个数-1
            }
        }
        else if(str.size()==4){
            cin>>m;
            q[tt++]=m;
            add(m,1); // 表示目前可以取的数字中x个数+1
        }
        else{
            if(!tt) {
                puts("Invalid");
                continue;
            }
            int k;
            if(tt%2){
                k=(tt+1)/2; // k：计算中值这个数字是第几小的数字
            }
            else if(tt%2==0){
                k=tt/2;
            }
            int l=0,r=N;
            while(l<r){  // 二分查找一下，在（0~N）中第k小的数字是哪个，该数字就是中值
                int mid=(l+r)/2;
                if(sum(mid) >=k) r=mid;
                else l=mid+1;
            }
            cout<<r<<endl;
        }
    }
    system("pause");
    return 0;
}