题解：P7072 [CSP-J2020] 直播获奖

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10, INF = 1e3;

int n, p;
struct Node
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N];
int root, idx;

void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

int get_node(int key)
{
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(1);
    if (tr[1].val < tr[2].val)
        zag(root);
}

void insert(int &p, int key)
{
    if (!p)
        p = get_node(key);
    else if (tr[p].key == key)
        tr[p].cnt ++;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val)
            zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val)
            zag(p);
    }
    
    pushup(p);
}

int query_key(int p, int rank)
{
    if (!p)
        return INF;
    if (tr[tr[p].l].size >= rank)
        return query_key(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank)
        return tr[p].key;
    return query_key(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    build();
    
    cin >> n >> p;
    for (int i = 1; i <= n; ++ i )
    {
        int x;
        cin >> x;
        int k = min(i, i - int(p * 0.01 * i) + 1);
        insert(root, x);
        cout << query_key(root, k + 1) << ' ';
    }
    
    return 0;
}