社区讨论
样例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 条回复,欢迎继续交流。
正在加载回复...