二次联通门 : BZOJ 1503: [NOI2004]郁闷的出纳员
/*
BZOJ 1503: [NOI2004]郁闷的出纳员 考虑这样一个事实
无论是加或减
都是针对全体人员的 那么只需要记录一个总标记 直接记录对于工资的加或减 每次查询最低要求工资与标记的差的前驱，并旋到根处 那么根节点的所有左子树都是不符合要求要走人的
每次记录一下搞一搞， 就不用考虑splay麻烦的标记下放问题了
但是却没调出来。。。
*/
#include <cstdio> void read (int &now)
{
register char word = getchar ();
bool temp = false;
for (now = ; word < '' || word > ''; word = getchar ())
if (word == '-')
temp = true;
for (; word >= '' && word <= ''; now = now * + word - '', word = getchar ());
if (temp)
now = -now;
} int Min_N; struct S_D
{
S_D *child[], *father; int key;
int weigth, size; inline void Updata ()
{
this->size = this->weigth;
if (this->child[])
this->size += this->child[]->size;
if (this->child[])
this->size += this->child[]->size;
} S_D ()
{
child[] = child[] = NULL;
size = weigth = ;
key = ;
father = NULL;
} inline int Get_Pos ()
{
return this->father->child[] == this;
} inline void Clear ()
{
this->child[] = this->child[] = father = NULL;
}
}; int Answer;
class Splay_Tree_Type
{ private : S_D *Root; inline void Rotate (S_D *now)
{
S_D *Father = now->father;
register int pos = now->Get_Pos () ^ ;
Father->child[pos ^ ] = now->child[pos];
if (now->child[pos])
now->child[pos]->father = Father;
if ((now->father = Father->father) != NULL)
now->father->child[now->father->child[] == Father] = now; Father->father = now;
now->child[pos] = Father; Father->Updata ();
now->Updata (); if (now->father == NULL)
Root = now;
} inline void Splay (S_D *now)
{
for (S_D *Father; Father = now->father; this->Rotate (now))
if (Father->father != NULL)
this->Rotate (now->Get_Pos () == Father->Get_Pos () ? Father : now);
} S_D* Find (int x)
{
S_D *now = Root;
for (; (now != NULL && now->key != x); now = now->child[x > now->key]);
if (now == NULL)
return now;
Splay (now);
return now;
} void Delete_point (int x)
{
S_D *now = Find (x);
if (now->weigth > )
{
now->weigth --;
return ;
}
if (now->child[] == NULL && now->child[] == NULL)
{
now->Clear ();
Root = NULL;
return ;
}
S_D *res;
if (now->child[] == NULL)
{
Root = now->child[];
now->child[]->father = NULL;
now->Clear ();
return ;
}
if (now->child[] == NULL)
{
Root = now->child[];
now->child[]->father = NULL;
now->Clear ();
return ;
}
S_D *Prefix = Find_Prefix (x);
res = Root;
Prefix->child[] = res->child[];
res->child[]->father = Root;
res->Clear ();
Root->Updata ();
} void Delete_tree (int x)
{
S_D *now = Find_Suffix (x);
if (now == NULL)
return ;
Answer += now->child[]->size;
now->child[]->father = NULL;
now->child[] = NULL;
now->Updata ();
} S_D *Find_Suffix (int x)
{
this->Insert (x);
S_D *now = Root;
if (now->child[] == NULL)
{
this->Delete_point (x);
return NULL;
}
for (now = now->child[]; now->child[]; now = now->child[]);
this->Delete_point (x);
if (now == NULL)
return now;
this->Splay (now);
return now;
} S_D *Find_Prefix (int x)
{
this->Insert (x);
S_D *now = Root;
if (now->child[] == NULL)
{
this->Delete_point (x);
return NULL;
}
for (now = now->child[]; now->child[]; now = now->child[]);
this->Delete_point (x);
if (now == NULL)
return now;
this->Splay (now);
return now;
} public : int Flandre_Scarlet; void Insert (int x)
{
if (Root == NULL)
{
Root = new S_D ;
Root->key = x;
return ;
}
S_D *now = Root, *Father;
for (; ;Father = now, now = now->child[x > now->key])
{
if (now == NULL)
{
now = new S_D;
now->key = x;
now->father = Father;
Father->child[x > Father->key] = now;
this->Splay (now);
return ;
}
if (x == now->key)
{
now->weigth ++;
this->Splay (now);
return ;
}
}
} void Cut (int x)
{
int Need = Min_N - Flandre_Scarlet;
S_D *now = this->Find_Prefix (Need);
if (now != NULL)
this->Delete_tree (now->key);
} int Query (int x)
{
S_D *now = Root;
for (register int res = ; ; )
{
if (now->child[] && x < now->child[]->size)
now = now->child[];
res += (now->child[] ? now->child[]->size : ) + now->weigth;
if (x <= res)
return now->key;
x -= res;
now = now->child[];
}
} void Change (int x)
{
Flandre_Scarlet += x;
return ;
} int Query_Size ()
{
return Root->size;
}
}; Splay_Tree_Type Splay; int main (int argc, char *argv[])
{
freopen ("cashier.in", "r", stdin);
freopen ("cashier.out", "w", stdout);
int N;
read (N);
read (Min_N);
char type[];
register int Size;
for (int x; N --; )
{
scanf ("%s", type);
read (x);
if (type[] == 'I')
Splay.Insert (x);
else if (type[] == 'S')
Splay.Change (-x);
else if (type[] == 'A')
Splay.Change (x);
else
{
Splay.Cut (x);
Size = Splay.Query_Size ();
if (x > Size)
puts ("-1");
else
printf ("%d\n", Splay.Query (Size - x) + Splay.Flandre_Scarlet);
}
}
printf ("%d", Answer);
return ;
} /*
20 0
I 4
F 1
I 6
S 9
F 14
I 6
I 7
A 8
I 3
F 2
I 9
I 6
I 6
S 3
S 5
I 6
F 1
I 3
A 2
F 5
*/ /*
4
-1
14
7
3
5
*/