treap..
有几个地方写的很尴尬...
其实我没写过平衡树...任何的平衡树..
所以我就把对于size的维护写错了..orz..
然后我又把砍掉一棵子树那部分写错了..
我感觉这样砍树是会造成一定的不平衡的..
但不平衡会很小.
呃..其实也不能这么说..
应该说..会造成不平衡..
但这个不平衡带给我的负担不会高于我曾经的负担..orz..貌似是这样
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
#define RANK_L(x) ((x)->left==NULL?0:(x)->left->size)
#define RANK_R(x) ((x)->right==NULL?0:(x)->right->size)
ifstream fin("cashier.in");
ofstream fout("cashier.out");
int delta=0,leave=0;
const int MAXN=100001;
int num=0;
struct node
{
int father,size,value,ran;
node *left,*right;
} *root,tree[MAXN+1];
int n,m_in;
int len=0;
int _count=0;
/**//*
a
/ \
c b
/ \
d e
*/
void RotateLeft(node* &x)
{
node *z=x->right;
z->size=x->size;
x->right=z->left;
z->left=x;
x->size=RANK_L(x)+RANK_R(x)+1;
x=z;
}
void RotateRight(node* &x)
{
node *z=x->left;
z->size=x->size;
x->left=z->right;
z->right=x;
x->size=RANK_R(x)+RANK_L(x)+1;
x=z;
}
void insert(node *&x,int k)
{
if (x==NULL)
{
node *p=&tree[len++];
p->value=k;
p->ran=rand()*rand();
p->size=1;
p->left=NULL;
p->right=NULL;
x=p;
return;
}
x->size++;
if (k>=x->value)
{
insert(x->right,k);
if (x->right->ran>x->ran) RotateLeft(x);
}
else
{
insert(x->left,k);
if (x->left->ran>x->ran) RotateRight(x);
}
}
int _delete(node *&x)
{
int v=0,t=0;
if (x==NULL) return 0;
if (x->value+delta<m_in)
{
v+=RANK_L(x)+1;
x->size-=v;
x->left=NULL;
t=_delete(x->right);
v+=t;
x->size-=t;
if (x->right!=NULL) x->right->size=x->size;
x=x->right;
}
else
{
t=_delete(x->left);
v=t;
x->size-=t;
}
return v;
}
int find(node *x,int k)
{
if (x==NULL) return 0;
if (k==RANK_R(x)+1) return x->value;
if (k>RANK_R(x)) return find(x->left,k-RANK_R(x)-1);
else
return find(x->right,k);
}
int total;
int main()
{
root=NULL;
fin>>n>>m_in;
for (int i=1;i<=n;i++)
{
char c,ch;
int k;
fin>>c>>k;
switch(c)
{
case 'I':if (k>=m_in) {total++;insert(root,k-delta);}break;
case 'A':delta+=k;break;
case 'S':delta-=k;_count=_delete(root);num+=_count;break;
case 'F':if (k>total-num) fout<<-1<<endl; else fout<<find(root,k)+delta<<endl;break;
default:break;
}
}
fout<<num<<endl;
return 0;
}