P4291 [HAOI2008] 排名系统 - 洛谷

题目一看就像数据结构，再看一眼数据范围，行，肯定是  的时间复杂度。

有  那就是树形的数据结构，插入，查询排名，按排名查询 10 个，考虑 FHQ。

不会 FHQ 的出门右转：【笔记 & 题解 | FHQ Treap（可持久化）】洛谷P3369【模板】普通平衡树 & 洛谷 P3835 【模板】可持久化平衡树_p3369 【模板】普通平衡树 fhq-CSDN博客

---

对于插入人名操作，我们建一个 map<string, ？> 来映射每个名字对应的权值（比赛分数）。

对于查询排名操作，我们先映射到人名对应的权值，使用 getrnk 函数，

分割一颗小于当前权值的树和一颗大于等于当前权值的树，取第一棵树的 siz + 1。

但注意到：

如果两个玩家的得分相同，则先得到该得分的玩家排在前面。

也就是相同权值，按时间戳排序。

我们知道，普通的平衡树，在分割的时候满足以下条件：

而查询时，只是暴力的分割成两棵树取 siz，也就是说，

普通平衡树对于所有相同值的查询，输出的排名都是一样的。

有人会说，那把那个保证平衡的随机数，改成时间戳不就行了？

不，随机数只能保证平衡。换句话说，它只能决定谁当父亲节点，不能决定排名。

请看合并代码：

int merge(int x, int y) {
    if ( (!x) || (!y) ) return x + y;   //空树情况，当 x和 y其中一方为 0，那输出另一方 
    // 优先级 rnd 较小的节点作为根，保证树的平衡
    if (tr[x].rnd < tr[y].rnd) {   
        rc(x) = merge(rc(x), y);  // 将 y合并到 x的右子树
        pushup(x);
        return x;
    }
    else {
        lc(y) = merge(x, lc(y));  // 将 x合并到 y的左子树
        pushup(y);
        return y;
    }
}

我们只会将随机数小的放到父亲节点，而不会在分裂的时候将它归入第一棵树。

事实上，无论怎么合并，整棵树的中序遍历是不变的，是有序的序列。

解决方法也很简单，将原来按权值分裂改成第一关键字权值，第二关键字时间戳。

可以使用系统自带的 pair<int, int>，自动排序比大小。

对于按排名查询最多 10 名玩家操作，当然可以先根据排名找到玩家，再连续输出 10 个后继。

但更常用（且常数小）的方法是，按排名分裂成三棵树，这样中间那棵树的中序遍历就是答案。

注释代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 25e4 + 10;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
typedef pair<int, int> PII;

struct node {
	int ls, rs;
	PII val;
	int siz;
	int rnd;
} tr[N];
int trlen, root;

void pushup(int p) {
	tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz + 1;
}

void split_val(int p, PII v, int &x, int &y) {
	if (p == 0) {
		x = y = 0;
		return ;
	}
	if (tr[p].val <= v) {
		x = p;
		split_val(rc(p), v, rc(x), y);
	}
	else {
		y = p;
		split_val(lc(p), v, x, lc(y));
	}
	pushup(p);
}

// split_rnk 分割后 
// x：中序遍历的前 k 个节点（即序列的前 k 项）
// y：中序遍历的第 k + 1 个及之后的所有节点（即序列的剩余部分）
void split_rnk(int p, int k, int &x, int &y) {
	if (p == 0) {
		x = y = 0;
		return ;
	}
	if (tr[lc(p)].siz + 1 <= k) {   // 分割线在 p 的右子节点 
		x = p;
		split_rnk(rc(p), k - tr[lc(p)].siz - 1, rc(x), y);
	}
	else {                         // 分割线在 p 的左子节点 
		y = p;
		split_rnk(lc(p), k, x, lc(y));
	}
	pushup(p);
}

int merge(int x, int y) {
	if (x == 0 || y == 0) {
		return x + y;
	}
	if (tr[x].rnd < tr[y].rnd) {
		rc(x) = merge(rc(x), y);
		pushup(x);
		return x;
	}
	else {
		lc(y) = merge(x, lc(y));
		pushup(y);
		return y;
	}
}

map<string, PII> mp;
map<PII, string> r_mp;

int new_tr(PII v) {
	trlen ++;
	tr[trlen] = {0, 0, v, 1, rand()};
	return trlen;
}

void ins(PII v) {
	int x, y;
	split_val(root, v, x, y);
	root = merge(merge(x, new_tr(v)), y);
}

void del(PII v) {
	int x, y, z;
	PII _v = {v.first, v.second - 1};   // 刚好在 v 前一个 
	split_val(root, _v, x, y);
	split_val(y, v, y, z);
	root = merge(x, z);
}

int get_rnk(PII v) {
	int x, y;
	split_val(root, v, x, y);   
	// v 是唯一的，直接搜寻到并输出 x 的字数大小 
	int res = tr[x].siz;
	root = merge(x, y);
	return res;
}

void print_10name(int p) {
	if (p == 0) {
		return ;
	}
	print_10name(lc(p));
	cout << r_mp[tr[p].val] << " ";
	print_10name(rc(p));
}

void get_10name(int k) {
	int x, y, z;
	int total = tr[root].siz;
	int r = min(k + 9, total);
	int len = r - k + 1;
	
	split_rnk(root, k - 1, x, y);   // x: [1, k - 1], y: [k, end]
	split_rnk(y, len, y, z);        // y: [k, r] (共 len 个)
	print_10name(y);
	cout << "\n";
	root = merge(merge(x, y), z); 
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	trlen = root = 0;
	
	for (int i = 1; i <= n; i ++) {
		string s;
		cin >> s;
		if (s[0] == '+') {
			string name = s.substr(1);   // 从 s 的第一位开始读 
			int v;
			cin >> v;
			PII x = {-v, i};  // 系统里面是从小到大排，我们要求从大到小排 
			
			if (mp.count(name)) {    // 之前有值就先删了 
				del(mp[name]);
			}
			mp[name] = x;
			r_mp[x] = name;
			ins(x);
		}
		
		if (s[0] == '?' && !isdigit(s[1])) {   // 第一位不是数字 
			string name = s.substr(1);
			cout << get_rnk(mp[name]) << "\n";
		}
		
		if (s[0] == '?' && isdigit(s[1])) {
			int k = 0;
			for (int i = 1; s[i]; i ++) {
				k = k * 10 + (s[i] - '0');   // 转成数字 
			}
			get_10name(k);
		}
	}
	
	return 0;
}