Remmina 酱白天要做文化课，只能晚上来写题了，现在凌晨啦

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

const double alp = 1 - sqrt(2) * 0.5, bta = (1 - 2 * alp) / (1 - alp);

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct N {int s[2], d, sz;} e[NS << 1];

int n, root, sz;

stack<int> rub;

int New(int d)
{
int a;
if (rub.empty()) a = ++sz;
else {a = rub.top(); rub.pop();}
e[a].d = d, e[a].sz = 1, e[a].s[0] = e[a].s[1] = 0;
return a;
}

void Del(int a) {rub.push(a);}

void pup(int a)
{
if (!e[a].s[0]) return;
e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
e[a].d = e[e[a].s[1]].d;
}

void rot(int a, int x)
{
if (!e[a].s[0]) return;
int b = e[a].s[x ^ 1];
e[a].s[x ^ 1] = e[a].s[x], e[a].s[x] = e[e[a].s[x ^ 1]].s[x];
e[e[a].s[x ^ 1]].s[x] = e[e[a].s[x ^ 1]].s[x ^ 1];
e[e[a].s[x ^ 1]].s[x ^ 1] = b, pup(e[a].s[x ^ 1]), pup(a);
}

void mt(int a)
{
if (!e[a].s[0]) return;
int x;
if (e[e[a].s[0]].sz < e[a].sz * alp) x = 1;
else if (e[e[a].s[1]].sz < e[a].sz * alp) x = 0;
else return;
if (e[e[e[a].s[x]].s[x ^ 1]].sz >= e[e[a].s[x]].sz * bta)
rot(e[a].s[x], x ^ 1);
rot(a, x);
}

void Insert(int d, int& a)
{
if (!a) {a = New(d); return;}
if (!e[a].s[0])
{
e[a].s[0] = New(d), e[a].s[1] = New(e[a].d);
if (d > e[a].d) swap(e[a].s[0], e[a].s[1]);
}
else Insert(d, e[a].s[d > e[e[a].s[0]].d]);
pup(a), mt(a);
}

void Erase(int d, int& a)
{
if (!e[a].s[0]) {Del(a), a = 0; return;}
int x = (d > e[e[a].s[0]].d);
if (!e[e[a].s[x]].s[0])
{
if (e[e[a].s[x]].d != d) puts("Error!"), exit(0);
Del(e[a].s[x]), Del(e[a].s[x ^ 1]), e[a] = e[e[a].s[x ^ 1]];
}
else Erase(d, e[a].s[x]);
pup(a), mt(a);
}

int Order(int d, int a)
{
if (!e[a].s[0]) return 0;
if (e[e[a].s[0]].d < d) return Order(d, e[a].s[1]) + e[e[a].s[0]].sz;
return Order(d, e[a].s[0]);
}

int Kth(int k, int a)
{
if (!e[a].s[0]) return e[a].d;
if (e[e[a].s[0]].sz <= k) return Kth(k - e[e[a].s[0]].sz, e[a].s[1]);
return Kth(k, e[a].s[0]);
}

int Pre(int d, int a)
{
if (!e[a].s[0])
{
if (e[a].d < d) return e[a].d;
return INT_MIN;
}
if (e[e[a].s[0]].d < d) return max(e[e[a].s[0]].d, Pre(d, e[a].s[1]));
return Pre(d, e[a].s[0]);
}

int Nxt(int d, int a)
{
if (!e[a].s[0])
{
if (e[a].d > d) return e[a].d;
return INT_MAX;
}
if (e[e[a].s[0]].d > d) return Nxt(d, e[a].s[0]);
return Nxt(d, e[a].s[1]);
}

int main(int argc, char const* argv[])
{
IN(n);
for (int i = 1, o, x; i <= n; i += 1)
{
IN(o), IN(x);
if (o == 1) Insert(x, root);
else if (o == 2) Erase(x, root);
else if (o == 3) printf("%d\n", Order(x, root) + 1);
else if (o == 4) printf("%d\n", Kth(x - 1, root));
else if (o == 5) printf("%d\n", Pre(x, root));
else printf("%d\n", Nxt(x, root));
}
return 0;
}


#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

const int alp = 4;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct N {int s[2], d, sz;} e[NS << 1];

int n, root, sz;

stack<int> rub;

int New(int d)
{
int a;
if (rub.empty()) a = ++sz;
else {a = rub.top(); rub.pop();}
e[a].d = d, e[a].sz = 1, e[a].s[0] = e[a].s[1] = 0;
return a;
}

void Del(int a) {rub.push(a);}

void pup(int a)
{
if (!e[a].s[0]) return;
e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
e[a].d = e[e[a].s[1]].d;
}

int Mix(int a, int b)
{
int res = New(e[b].d);
e[res].s[0] = a, e[res].s[1] = b, pup(res);
return res;
}

void lrot(int a)
{
if (!e[a].s[0]) return;
int tmp = e[e[a].s[0]].s[0];
Del(e[a].s[0]), e[a].s[1] = Mix(e[e[a].s[0]].s[1], e[a].s[1]);
e[a].s[0] = tmp;
}

void rrot(int a)
{
if (!e[a].s[0]) return;
int tmp = e[e[a].s[1]].s[1];
Del(e[a].s[1]), e[a].s[0] = Mix(e[a].s[0], e[e[a].s[1]].s[0]);
e[a].s[1] = tmp;
}

void mt(int a)
{
if (!e[a].s[0]) return;
if (e[e[a].s[0]].sz > e[e[a].s[1]].sz * alp) lrot(a);
else if (e[e[a].s[1]].sz > e[e[a].s[0]].sz * alp) rrot(a);
if (e[e[a].s[0]].sz > e[e[a].s[1]].sz * alp)
rrot(e[a].s[0]), lrot(a);
else if (e[e[a].s[1]].sz > e[e[a].s[0]].sz * alp)
lrot(e[a].s[1]), rrot(a);
}

void Insert(int d, int& a)
{
if (!a) {a = New(d); return;}
if (!e[a].s[0])
{
e[a].s[0] = New(d), e[a].s[1] = New(e[a].d);
if (d > e[a].d) swap(e[a].s[0], e[a].s[1]);
}
else Insert(d, e[a].s[d > e[e[a].s[0]].d]);
pup(a), mt(a);
}

void Erase(int d, int& a)
{
if (!e[a].s[0]) {Del(a), a = 0; return;}
int x = (d > e[e[a].s[0]].d);
if (!e[e[a].s[x]].s[0])
{
if (e[e[a].s[x]].d != d) puts("Error!"), exit(0);
Del(e[a].s[x]), Del(e[a].s[x ^ 1]), e[a] = e[e[a].s[x ^ 1]];
}
else Erase(d, e[a].s[x]);
pup(a), mt(a);
}

int Order(int d, int a)
{
if (!e[a].s[0]) return 0;
if (e[e[a].s[0]].d < d) return Order(d, e[a].s[1]) + e[e[a].s[0]].sz;
return Order(d, e[a].s[0]);
}

int Kth(int k, int a)
{
if (!e[a].s[0]) return e[a].d;
if (e[e[a].s[0]].sz <= k) return Kth(k - e[e[a].s[0]].sz, e[a].s[1]);
return Kth(k, e[a].s[0]);
}

int Pre(int d, int a)
{
if (!e[a].s[0])
{
if (e[a].d < d) return e[a].d;
return INT_MIN;
}
if (e[e[a].s[0]].d < d) return max(e[e[a].s[0]].d, Pre(d, e[a].s[1]));
return Pre(d, e[a].s[0]);
}

int Nxt(int d, int a)
{
if (!e[a].s[0])
{
if (e[a].d > d) return e[a].d;
return INT_MAX;
}
if (e[e[a].s[0]].d > d) return Nxt(d, e[a].s[0]);
return Nxt(d, e[a].s[1]);
}

int main(int argc, char const* argv[])
{
IN(n);
for (int i = 1, o, x; i <= n; i += 1)
{
IN(o), IN(x);
if (o == 1) Insert(x, root);
else if (o == 2) Erase(x, root);
else if (o == 3) printf("%d\n", Order(x, root) + 1);
else if (o == 4) printf("%d\n", Kth(x - 1, root));
else if (o == 5) printf("%d\n", Pre(x, root));
else printf("%d\n", Nxt(x, root));
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 3 条评论

#### Remmina · 2019年1月7日 8:28 下午

能用 vector？那真是太妙了
我不会呀我还是太菜了