社区讨论

样例RE求助qwq

P2073送花参与者 3已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@lx6yty6k
此快照首次捕获于
2024/06/09 11:09
2 年前
此快照最后确认于
2024/06/09 14:53
2 年前
查看原帖
CPP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
bool is[maxn];
int n, x, w, c, op, ans, pri, now, tot, root;
struct npde {
	int l, r, b, rd, val, size;
} t[maxn];
void push_up(int now) {
	t[now].size = t[t[now].l].size + t[t[now].r].size + 1;
	return ;
}
void spilt(int now, int key, int &x, int &y) {
	if (now) {
		if (t[now].val <= key) {
			x = now;
			spilt(t[now].r, key, t[now].r, y);
		} else {
			y = now;
			spilt(t[now].l, key, x, t[now].l);
		}
		push_up(now);
	} else x = y = 0;
	return ;
}
int merge(int x, int y) {
	if (x && y) {
		if (t[x].rd <= t[y].rd) {
			t[x].r = merge(t[x].r, y);
			push_up(x);
			return x;
		} else {
			t[y].l = merge(x, t[y].l);
			push_up(y);
			return y;
		}
	}
	return x + y;
}
int new_node(int key, int b) {
	tot++;
	is[b] = true;
	t[tot].b = b;
	t[tot].l = t[tot].r = 0;
	t[tot].val = key;
	t[tot].size = 1;
	t[tot].rd = rand();
	return tot;
}
void insert(int key, int b) {
	int x, y;
	spilt(root, key, x, y);
	root = merge(merge(x, new_node(key, b)), y);
	return ;
}
void del(int key) {
	int x, y, z;
	spilt(root, key, x, y);
	spilt(x, key - 1, x, z);
	is[t[z].val] = false;
	z = merge(t[z].l, t[z].r);
	root = merge(merge(x, z), y);
	now--;
	return ;
}
int get_rank(int key) {
	int x, y;
	spilt(root, key - 1, x, y);
	int ans = t[x].size + 1;
	root = merge(x, y);
	return ans;
}
int get_key(int now, int k) {
	int cnt = t[t[now].l].size + 1;
	if (cnt == k) return t[now].val;
	else if (cnt < k) return get_key(t[now].r, k - cnt);
	return get_key(t[now].l, k);
}
int add(int now, int k) {
	int cnt = t[t[now].l].size + 1;
	if (cnt == k) return t[now].b;
	else if (cnt < k) return get_key(t[now].r, k - cnt);
	return get_key(t[now].l, k);
}
int main() {
	scanf("%d", &op);
	while (~op) {
		if (op == 1) {
			scanf("%d %d", &w, &c);
			if (is[c]) continue;
			insert(w, c);
		} else if (op == 2) del(get_key(root, 1));	
		else if (op == 3) del(get_key(root, now));
		scanf("%d", &op);
	}
	while (now) {
		ans += add(root, 1);
		pri += get_key(root, 1);
		del(get_key(root, 1));
	}
	printf("%d %d\n", ans, pri);
	return 0;
}

回复

12 条回复,欢迎继续交流。

正在加载回复...