LYDSY 3224_SCAPEGOAT
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
inline int max(int a, int b) { return a > b ? a : b; }
const int maxn = 100005;
int val[maxn], lch[maxn], rch[maxn], sz[maxn], cap[maxn], arr[maxn], aend, root, pool[maxn], idx = 1;
bool exist[maxn];
inline int newNode() { return pool[idx++]; }
inline void delNode(int x) { pool[--idx] = x; }
inline void setNode(int x, int v = 0) { val[x] = v, lch[x] = rch[x] = 0, exist[x] = true, sz[x] = cap[x] = 1; }
inline bool isBad(int x)
{
return (sz[x] + 5 < cap[x] >> 1) ||
(max(sz[lch[x]], sz[rch[x]]) - 5 > (sz[x] * 3) >> 2);
}
inline void update(int x)
{
sz[x] = sz[lch[x]] + sz[rch[x]] + exist[x];
cap[x] = cap[lch[x]] + cap[rch[x]] + 1;
}
void rebuild_impl(int x)
{
if (x == 0) return;
rebuild_impl(lch[x]);
if (exist[x]) arr[aend++] = val[x];
rebuild_impl(rch[x]);
delNode(x);
}
void rebuild_impl(int &x, int b, int e)
{
if (b < e)
{
setNode(x = newNode(), 0);
int m = (b + e) >> 1;
val[x] = arr[m];
rebuild_impl(lch[x], b, m);
rebuild_impl(rch[x], m + 1, e);
update(x);
}
}
inline void rebuild(int &x)
{
if (x == 0) return;
aend = 0;
rebuild_impl(x);
rebuild_impl(x, 0, aend);
}
int rnk(int x)
{
int cur = root, ans = 1;
while (cur)
if (x <= val[cur])
cur = lch[cur];
else
ans += sz[lch[cur]] + exist[cur], cur = rch[cur];
return ans;
}
int kth(int x)
{
int cur = root;
while (cur)
{
if (sz[lch[cur]] + 1 == x && exist[cur])
break;
else if (sz[lch[cur]] >= x)
cur = lch[cur];
else
x -= sz[lch[cur]] + exist[cur], cur = rch[cur];
}
return val[cur];
}
int *insert_impl(int &node, int x)
{
int *res = 0;
if (node == 0)
setNode(node = newNode(), x);
else
{
res = insert_impl(x < val[node] ? lch[node] : rch[node], x);
update(node);
if (isBad(node)) res = &node;
}
return res;
}
int *delete_impl(int &node, int x)
{
if (node == 0) return 0;
int *ret = 0;
sz[node]--;
int pos = sz[lch[node]] + exist[node];
if (pos == x && exist[node])
exist[node] = false;
else
{
ret = x <= pos ? delete_impl(lch[node], x) : delete_impl(rch[node], x - pos);
update(node);
if (isBad(node)) ret = &node;
}
return ret;
}
void ins(int x)
{
int *ret = insert_impl(root, x);
if (ret) rebuild(*ret);
}
void del(int x)
{
int rk = rnk(x);
if (x != kth(rk)) return;
int *ret = delete_impl(root, rk);
if (ret) rebuild(*ret);
}
int main()
{
for (int i = 0; i < maxn; i++) pool[i] = i;
int n;
scanf("%d", &n);
for (int i = 0, op, x; i < n; i++)
{
scanf("%d%d", &op, &x);
if (op == 1) ins(x);
if (op == 2) del(x);
if (op == 3) printf("%d\n", rnk(x));
if (op == 4) printf("%d\n", kth(x));
if (op == 5) printf("%d\n", kth(rnk(x) - 1));
if (op == 6) printf("%d\n", kth(rnk(x + 1)));
}
return 0;
}