[luogu2584]:[ZJOI2006]GameZ游戏排名系统

[luogu2584]:[ZJOI2006]GameZ游戏排名系统

题目链接

信仰圣光吧


Solution

当两个玩家的名次相同时,先上传记录者优先。是这个题的核心。

我们考虑到权值在1e10以内,而且其操作数不可能超过1e8,那么不妨将其权值乘以1e8在加上n减去操作的次数就好了

我以为询问10名的名字是什么很nb的操作,原来是暴力的10logn,emmmmmmm


Code

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<map>
#include<iostream>
#include<cstring>

using namespace std;

typedef long long ll;
const int N = 5e5;
const ll base = 1e8;
struct Node {
    ll siz, val, rnd;
    string name;
    Node *ch[2];
    void maintain() {
        siz = ch[0]->siz + ch[1]->siz + 1;
    }
} pool[N], *root, *null, *rt1, *rt2, *rt3;
std::map<string, ll> hsh;

inline ll read() {
    char c = getchar(); ll x = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    do {x = x * 10 + (c ^ 48); c = getchar();} while(isdigit(c));
    return x * f;
}

void init() {
    null = &pool[0];
    null->siz = null->val = null->rnd = 0;
    null->ch[0] = null->ch[1] = NULL;
    root = null;
}

void split(Node *o, ll k, Node *&x, Node *&y) {
    if(o == null) x = y = null;
    else {
        if(o->val <= k) {
            x = o; split(o->ch[1], k, o->ch[1], y);
        } else {
            y = o; split(o->ch[0], k, x, o->ch[0]);
        }
        o->maintain();
    }
}

Node *merge(Node *x, Node *y) {
    if(x == null) return y;
    if(y == null) return x;
    if(x->rnd < y->rnd) {
        x->ch[1] = merge(x->ch[1], y);
        x->maintain(); return x;
    } else {
        y->ch[0] = merge(x, y->ch[0]);
        y->maintain(); return y;
    }
}

Node *newNode(ll v, string idx) {
    static int cnt = 1;
    pool[cnt].siz = 1; pool[cnt].rnd = rand();
    pool[cnt].val = v; pool[cnt].name = idx;
    pool[cnt].ch[0] = pool[cnt].ch[1] = null;
    return &pool[cnt++];
}

void del(ll x) {
    split(root, x, rt1, rt2);
    split(rt1, x - 1, rt1, rt3);
    root = merge(rt1, rt2);
}

void insert(ll x, string name) {
    split(root, x, rt1, rt2);
    root = merge(merge(rt1, newNode(x, name)), rt2);
}

Node *kth(Node *o, int k) {
    if(o->ch[0]->siz >= k) return kth(o->ch[0], k);
    if(o->ch[0]->siz + 1 == k) return o;
    return kth(o->ch[1], k - o->ch[0]->siz - 1);
}

int main() {
    init();
    srand(time(0));
    int n = read();
    for(int i = 1; i <= n; ++i) {
        string opt;
        cin >> opt;
        if(opt[0] == '+') {
            opt.erase(opt.begin());
            ll tmp = read() * base + n - i;
            if(hsh.count(opt)) {
                ll qwq = hsh[opt];
                del(qwq);
                hsh[opt] = tmp;
                insert(tmp, opt);
            } else {
                hsh[opt] = tmp;
                insert(tmp, opt);
            }
            continue;
        } 
        if(isdigit(opt[1])) {
            ll tmp = 0;
            opt.erase(opt.begin());
            int sz = opt.size();
            for(int j = 0; j < sz; ++j)
                tmp = (opt[j] - '0') + (tmp * 10);
            for(int j = 0; j < 10; ++j) {
                if(j + tmp > root->siz) break;
                cout << kth(root, root->siz - j - tmp + 1)->name << " ";
            }
            cout << endl;
        } else {
            opt.erase(opt.begin());
            ll x = hsh[opt];
            split(root, x, rt1, rt2);
            printf("%lld\n", rt2->siz + 1);
            root = merge(rt1, rt2);
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒