分块求第k大的数：

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 10;
const int sqrtN = 316;
int block[sqrtN], table[maxn];
int n;
stack<int>s;
void Pop()
{
    int x = s.top();
    s.pop();
    table[x]--;
    block[x / sqrtN]--;
    printf("%d\n", x);
}
void Push(int x)
{
    s.push(x);
    table[x]++;
    block[x / sqrtN]++;
}
void PeekMedian(int k)
{
    int sum = 0, idx = 0;
    while (sum + block[idx] < k)sum += block[idx++];
    int num = sqrtN*idx;
    while (sum + table[num] < k)sum += table[num++];
    printf("%d\n", num);
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        char ss[30];
        scanf("%s", ss);
        int num;
        if (ss[1] == 'o')
        {
            if (s.size() == 0)printf("Invalid\n");
            else Pop();
        }
        else if (ss[1] == 'e')
        {
            if (s.size() == 0)printf("Invalid\n");
            else
            {
                int k;
                if (s.size() % 2 == 0)k = s.size() / 2;
                else k = (s.size() + 1) / 2;
                PeekMedian(k);
            }
        }
        else if(ss[1]=='u')
        {
            scanf("%d", &num);
            Push(num);
        }
    }
    return 0;
}

树状数组：
c[i]表示lowbit[i]个数的个数

#include<iostream>
#include<stack>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int maxn = 1e5 + 10;
int c[maxn] = { 0 }, n;
stack<int>st;
void update(int x, int v)
{
    for (int i = x; i <= maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))ans += c[i];
    return ans;
}
void PeekMedian(int K)
{
    int l = 0, r = maxn;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (getsum(mid) >= K)r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        char s[10];
        scanf("%s", s);
        if (s[1] == 'o')
        {
            if (st.size() == 0)printf("Invalid\n");
            else
            {
                int x = st.top();
                st.pop();
                update(x, -1);
                printf("%d\n",x);
            }
        }
        else if (s[1] == 'u')
        {
            int num;
            scanf("%d", &num);
            st.push(num);
            update(num, 1);
        }
        else if (s[1] == 'e')
        {
            if (st.size() == 0)printf("Invalid\n");
            else
            {
                int k;
                if (st.size() % 2 == 0)k = st.size() / 2;
                else k = (st.size() + 1) / 2;
                PeekMedian(k);
            }
        }
    }
    return 0;
}