#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 2000010, inf = 1 << 30 | 1;
template <typename T>
inline void read(T &k)
{
int f = 1; k = 0; char c = getchar();
while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
k *= f;
}
enum ColorSet {Red, Black};
struct Node
{
int Val, Size, LT, RT, Fa;
bool Col;
// Node(int _Val) : Val(_Val)
// {
// Size = 1;
// LT = RT = Fa = Col = 0;
// };
}Tr[maxn];
int Root, Tot, n, ty, x, m;
inline void Update(int x)
{
Tr[x].Size = Tr[Tr[x].LT].Size + Tr[Tr[x].RT].Size + 1;
}
void LeftRotate(int x)
{
int RT = Tr[x].RT;
Tr[x].RT = Tr[RT].LT;
if (Tr[RT].LT)
Tr[Tr[RT].LT].Fa = x;
Tr[RT].Fa = Tr[x].Fa;
if (Tr[x].Fa)
if (Tr[Tr[x].Fa].LT == x)
Tr[Tr[x].Fa].LT = RT;
else
Tr[Tr[x].Fa].RT = RT;
else
Root = RT;
Tr[x].Fa = RT;
Tr[RT].LT = x;
Update(x); Update(RT);
}
void RightRotate(int x)
{
int LT = Tr[x].LT;
Tr[x].LT = Tr[LT].RT;
if (Tr[LT].RT)
Tr[Tr[LT].RT].Fa = x;
Tr[LT].Fa = Tr[x].Fa;
if (Tr[x].Fa)
if (Tr[Tr[x].Fa].RT == x)
Tr[Tr[x].Fa].RT = LT;
else
Tr[Tr[x].Fa].LT = LT;
else
Root = LT;
Tr[x].Fa = LT;
Tr[LT].RT = x;
Update(x); Update(LT);
}
int Find(int Val, int ty = 0)
{
int x = Root, Fa = 0;
while (x)
{
Fa = x;
if (!ty && Tr[x].Val == Val) return x;
x = Tr[x].Val < Val ? Tr[x].RT : Tr[x].LT;
}
return Fa;
}
inline void newnode(int x, int Val)
{
Tr[x].Size = 1;
Tr[x].Val = Val;
Tr[x].LT = Tr[x].RT = Tr[x].Col = Tr[x].Fa = 0;
}
void Insert(int Val)
{
int x = ++Tot;
newnode(x, Val);
// Tr[x] = Node(Val);
int Fa = Find(Val, 1);
Tr[x].Fa = Fa;
if (Fa)
if (Tr[Fa].Val < Val)
Tr[Fa].RT = x;
else
Tr[Fa].LT = x;
else
Root = x;
int y = Fa;
while (y)
++Tr[y].Size, y = Tr[y].Fa;
while (Fa && Tr[Fa].Col == Red)
{
int Gfa = Tr[Fa].Fa;
int Unc = (Fa == Tr[Gfa].LT) ? Tr[Gfa].RT : Tr[Gfa].LT;
if (Unc && Tr[Unc].Col == Red)
{
Tr[Fa].Col = Tr[Unc].Col = Black;
Tr[Gfa].Col = Red;
x = Gfa; Fa = Tr[x].Fa;
}
else
{
if (Fa == Tr[Gfa].LT)
{
if (x == Tr[Fa].RT)
LeftRotate(Fa), swap(x, Fa);
Tr[Fa].Col = Black;
Tr[Gfa].Col = Red;
RightRotate(Gfa);
}
else
{
if (x == Tr[Fa].LT)
RightRotate(Fa), swap(x, Fa);
Tr[Fa].Col = Black;
Tr[Gfa].Col = Red;
LeftRotate(Gfa);
}
}
}
if (!Fa && Tr[x].Col == Red)
Tr[x].Col = Black;
}
void Erase(int x)
{
int Fa = Tr[x].Fa, p, DelCol = Tr[x].Col;
if (!Tr[x].LT)
{
int RT = Tr[x].RT;
p = RT;
if (Fa)
if (Tr[Fa].LT == x)
Tr[Fa].LT = RT;
else
Tr[Fa].RT = RT;
else
Root = RT;
if (RT)
Tr[RT].Fa = Fa;
}
else if (!Tr[x].RT)
{
int LT = Tr[x].LT;
p = LT;
if (Fa)
if (Tr[Fa].LT == x)
Tr[Fa].LT = LT;
else
Tr[Fa].RT = LT;
else
Root = LT;
if (LT)
Tr[LT].Fa = Fa;
}
else
{
int y = Tr[x].RT;
while (Tr[y].LT)
y = Tr[y].LT;
DelCol = Tr[y].Col;
int RT = Tr[y].RT;
p = RT;
if (Tr[y].Fa != x)
{
Fa = Tr[y].Fa;
Tr[Fa].LT = Tr[y].RT;
if (Tr[y].RT)
Tr[Tr[y].RT].Fa = Fa;
Tr[y].RT = Tr[x].RT;
Tr[Tr[x].RT].Fa = y;
}
else
Fa = y;
if (Tr[x].Fa)
if (Tr[Tr[x].Fa].LT == x)
Tr[Tr[x].Fa].LT = y;
else
Tr[Tr[x].Fa].RT = y;
else
Root = y;
Tr[y].Fa = Tr[x].Fa;
Tr[y].LT = Tr[x].LT;
Tr[Tr[x].LT].Fa = y;
Tr[y].Col = Tr[x].Col;
Tr[y].Size = Tr[x].Size;
}
int y = Fa;
while (y)
--Tr[y].Size, y = Tr[y].Fa;
if (DelCol == Black)
{
x = p;
while (x != Root && (!x || Tr[x].Col == Black))
{
if (x == Tr[Fa].LT)
{
int Bro = Tr[Fa].RT;
if (Tr[Bro].Col == Red)
{
Tr[Bro].Col = Black;
Tr[Fa].Col = Red;
LeftRotate(Fa);
Bro = Tr[Fa].RT;
}
if ((!Tr[Bro].LT || Tr[Tr[Bro].LT].Col == Black) && (!Tr[Bro].RT || Tr[Tr[Bro].RT].Col == Black))
{
Tr[Bro].Col = Red;
x = Fa;
Fa = Tr[x].Fa;
}
else
{
if (!Tr[Bro].RT || Tr[Tr[Bro].RT].Col == Black)
{
int Nie = Tr[Bro].LT;
Tr[Nie].Col = Black;
Tr[Bro].Col = Red;
RightRotate(Bro);
Bro = Nie;
}
Tr[Bro].Col = Tr[Fa].Col;
Tr[Fa].Col = Black;
Tr[Tr[Bro].RT].Col = Black;
LeftRotate(Fa);
x = Root;
}
}
else
{
int Bro = Tr[Fa].LT;
if (Tr[Bro].Col == Red)
{
Tr[Bro].Col = Black;
Tr[Fa].Col = Red;
RightRotate(Fa);
Bro = Tr[Fa].LT;
}
if ((!Tr[Bro].RT || Tr[Tr[Bro].RT].Col == Black) && (!Tr[Bro].LT || Tr[Tr[Bro].LT].Col == Black))
{
Tr[Bro].Col = Red;
x = Fa;
Fa = Tr[x].Fa;
}
else
{
if (!Tr[Bro].LT || Tr[Tr[Bro].LT].Col == Black)
{
int Nie = Tr[Bro].RT;
Tr[Nie].Col = Black;
Tr[Bro].Col = Red;
LeftRotate(Bro);
Bro = Nie;
}
Tr[Bro].Col = Tr[Fa].Col;
Tr[Fa].Col = Black;
Tr[Tr[Bro].LT].Col = Black;
RightRotate(Fa);
x = Root;
}
}
}
if (x)
Tr[x].Col = Black;
}
}
int Get_Rank(int Val)
{
int Rank = 0, x = Root;
while (x)
{
if (Val > Tr[x].Val)
Rank += Tr[Tr[x].LT].Size + 1, x = Tr[x].RT;
else
x = Tr[x].LT;
}
return Rank;
}
int Get_Kth(int K)
{
int x = Root;
while (x)
{
if (K == Tr[Tr[x].LT].Size + 1)
return Tr[x].Val;
if (K <= Tr[Tr[x].LT].Size)
x = Tr[x].LT;
else
K -= Tr[Tr[x].LT].Size + 1, x = Tr[x].RT;
}
return inf;
}
int Get_Pre(int Val)
{
int x = Root, ans = 0;
while (x)
{
if (Val > Tr[x].Val)
ans = Tr[x].Val, x = Tr[x].RT;
else
x = Tr[x].LT;
}
return ans;
}
int Get_Next(int Val)
{
int x = Root, ans = 0;
while (x)
{
if (Val < Tr[x].Val)
ans = Tr[x].Val, x = Tr[x].LT;
else
x = Tr[x].RT;
}
return ans;
}
int main()
{
n = 500000;
int a[n + 1];
for (int i = 1; i <= n; i++)
Insert(a[i] = rand());
for (int i = 1; i <= n; i++)
Erase(Find(a[i]));
// read(n);
// for (int i = 1; i <= n; i++)
// {
// read(ty); read(x);
// if (ty == 1) Insert(x);
// else if (ty == 2) Erase(Find(x));
// else if (ty == 3) printf("%d\n", Get_Rank(x) + 1);
// else if (ty == 4) printf("%d\n", Get_Kth(x));
// else if (ty == 5) printf("%d\n", Get_Pre(x));
// else printf("%d\n", Get_Next(x));
// }
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 282.253 ms | 13 MB + 396 KB | Wrong Answer | Score: 0 | 显示更多 |