| 记录编号 |
558535 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[Tyvj 1728]普通平衡树 |
最终得分 |
100 |
| 用户昵称 |
 Satoshi |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.323 s |
| 提交时间 |
2021-01-06 22:51:20 |
内存使用 |
1.73 MiB |
显示代码纯文本
//#include <fstream>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("phs.in");
//ofstream cout("phs.out");
namespace TreapSpace
{
//start TreapSpace
inline void pw(int depth){while(depth--)cout<<" ";}//helper print function
template<typename Key, typename Value,bool ismul> //ismul: true->can have repeated key, false-> can not
class treap
{
public:
class node
{
public:
//Start: relationship
node *lc, *rc;
node *fa;//extra
//end: relationship
int p, sz;
Key key;
Value value,reval;
int depth;//extra
node(){p=sz=0;lc=rc=fa=NULL;}
node(Key a, Value b)
{
sz = 1;
key = a;reval = value = b;
p = (rand()<<13+rand());
lc = rc = fa = NULL;
depth = 1;
}
void print(int d=0)
{
pw(d);cout<<"data: "<<" lc: "<<lc<<" rc: "<<rc<<" fa: "<<fa<<" p: "<<p<<" size: "<<sz;
cout<<" depth: "<<depth;//extra
cout<<endl;
pw(d);cout<<"key, value, reduceval: "<<key<<' '<<value<<' '<<reval<<endl;
}
#define lc(x) x->lc
#define rc(x) x->rc
#define key(x) x->key
#define value(x) x->value
#define reval(x) x->reval
#define sz(x) x->sz
#define p(x) x->p
#define fa(x) x->fa
#define depth(x) x->depth//extra
};
inline node* new_node(Key a, Value b)
{
node* x = new node(a,b);
return x;
}
node* root;
//start: queries
int Size()
{
if(!root)return 0;
return sz(root);
}
Value Reval(){return reval(root);}
unsigned long long Sizeof()//memory cost of entire treap
{
return (unsigned long long)(sizeof(node) + sizeof(node*))*sz(root) + sizeof(node*);
}
//end: queries
//start: treap construction
treap(){root = NULL;}
treap(node *x){root = x;}//build a treap for existing node
treap(Key a, Value b){root = new_node(a,b);}//singleton
//end: treap construction
//Start: data preservation
inline void pushup(node* x){
if(!x)return ;
if(lc(x))
{
sz(x) = sz(lc(x)) + 1;
reval(x) = reval(lc(x)) + value(x);
fa(lc(x)) = x;
depth(x) = depth(lc(x)) + 1;
}
else
{
sz(x) = 1;
reval(x) = value(x);
depth(x) = 1;
}
if(rc(x))
{
sz(x) = sz(x) + sz(rc(x));
reval(x) = reval(x) + reval(rc(x));
fa(rc(x)) = x;
depth(x) = max(depth(x), depth(rc(x)) + 1);
}
}
inline void pushupRoot(node* x)//pushup all the way to the root
{
if(!x)return ;
while(x)
{
pushup(x);
x=fa(x);
}
}
//end: data preservation
//start: core operation
node* join(node* x, node* y)
{
if(!x)return y;
if(!y)return x;
if(p(x) > p(y))
{
rc(x) = join(rc(x), y);
pushup(x);
return x;
}
else
{
lc(y) = join(x, lc(y));
pushup(y);
return y;
}
}
//mode:true->equal to the left tree,
// false->equal to the right tree
void split(node* s, Key key, node* &x, node* &y,bool mode = true)
{
if(!s)
{
x = y = NULL;
return ;
}
if(mode)
{
if (key < key(s))split(lc(s), key, x, lc(s), mode), y = s;
else split(rc(s),key, rc(s), y, mode), x = s;
}
else
{
if (key(s) < key)split(rc(s), key, rc(s), y, mode), x = s;
else split(lc(s),key, x, lc(s), mode), y = s;
}
pushup(s);
}
inline node* join3(node *l, node *mid, node *r){
return join(join(l,mid),r);
}
inline void split3(Key a, node *&l, node *&mid, node *&r){
node *LL;
split(root, a, LL, r, true);
split(LL, a, l, mid, false);
}
inline void splitrange(Key a, Key b, node *&l, node *&mid, node *&r)
{
node *LL;
split(root, b, LL, r, true);
split(LL, a, l, mid, false);
}
//end: core operation
//start: basic BST functions
node* find(Key key)
{
node* x = root;
while(x)
{
if(key == key(x))break;
else if(key < key(x)) x = lc(x);
else x = rc(x);
}
return x;
}
void insert(node* x)
{
if(!x)
{
cout<<"insert an empty node!"<<endl;
return ;
}
node *y = find(key(x));
if(y && !ismul)return ;//no repeated node
node *L,*mid,*R; split3(key(x),L,mid,R);
if(ismul)root = join3(L,join(mid, x),R);
else root = join3(L,x,R);
}
void insert(Key a, Value b){insert(new_node(a,b));}
void replace(Key a, Value b)
{
node *x = find(a);
if(!x)
{
cout<<"replace an non-existed node!"<<endl;
exit(-1);
}
value(x) = b;
pushupRoot(x);
}
void erase(node* x)
{
if(!x)
{
cout<<"erase an empty node!"<<endl;
exit(-1);
}
node *L,*mid,*R; split3(key(x),L,mid,R);
if(!ismul)
{
delete mid;
root = join(L,R);
}
else
{
node* newmid = join(lc(mid),rc(mid));
root = join3(L,newmid,R);
delete mid;
}
}
void erase(Key a){erase(find(a));}
//end: basic BST functions
//start: range query
void getrange(Key a, Key b)//return the tree whose keys x, a<=x<=b, destructive
{
node *L,*mid,*R; splitrange(a,b,L,mid,R);
root = mid;
//destroy(L);
//destroy(R);
}
Value getrangeVal(Key a, Key b)//return the reduceVal whose keys x, a<=x<=b, pseudo non-destructive
{
Value ans;
node *L,*mid,*R; splitrange(a,b,L,mid,R);
ans = reval(mid);
root = join3(L,mid,R);//restore
return ans;
}
int getrangeSize(Key a, Key b)//return the total size whose keys x, a<=x<=b, pseudo non-destructive
{
Value ans;
node *L,*mid,*R; splitrange(a,b,L,mid,R);
ans = sz(mid);
root = join3(L,mid,R);//restore
return ans;
}
int count(Key a){return getrangeSize(a,a);}//return the number of times a certain key occurs
vector<node *> getrangeNode(Key a, Key b)//return the vector node x:V, such that a<=key(x)<=b
{
vector<node *> ans;
node *L,*mid,*R; splitrange(a,b,L,mid,R);
ans = allNode(mid);
root = join3(L,mid,R);
return ans;
}
void getNode(node *x, vector<node *> &ans)//return vector node in increasing order
{
if(!x)return;
getNode(lc(x),ans);
ans.push_back(x);
getNode(rc(x),ans);
}
inline vector<node *> allNode(node *x)
{
vector<node *> ans;
getNode(x,ans);
return ans;
}
vector<node *> allNode(){return allNode(root);}
//end: range query
//start: generic BST functions
node* begin()//minimum
{
node *x = root;
if(!x)return NULL;
while(lc(x))x = lc(x);
return x;
}
node* last()//maximum
{
node *x = root;
if(!x)return NULL;
while(rc(x))x = rc(x);
return x;
}
node* prev(node* x)//strictly small
{
node* y = lc(x);
if(y)
{
while(rc(y))y = rc(y);
return y;
}
else
{
y = fa(x);
while(y)
{
if(key(y) < key(x))return y;
y = fa(y);
}
}
return NULL;
}
node* prev(Key a)
{
node* x = root;
node* ans = NULL;
while(x)
{
if(key(x) < a)
{
if(!ans || key(ans) < key(x))ans = x;
x = rc(x);
}
else x = lc(x);
}
return ans;
}
node* next(node* x)//strictly larger
{
node* y = rc(x);
if(y)
{
while(lc(y))y = lc(y);
return y;
}
else
{
y = fa(x);
while(y)
{
if(!(key(y) < key(x) || key(y) == key(x)))return y;
y = fa(y);
}
}
return NULL;
}
node* next(Key a)
{
node* x = root;
node* ans = NULL;
while(x)
{
if(a < key(x))
{
if(!ans || key(x) < key(ans))ans = x;
x = lc(x);
}
else x = rc(x);
}
return ans;
}
//end generic BST functions
//start: root operation
node* findroot(node* x)//find the root
{
if(!x)return NULL;
while(fa(x))x = fa(x);
return x;
}
node* findroot(Key a){return findroot(find(a));}
void makeroot(node* x)//change the root to x
{
if(!x)
{
cout<<"this node does not exist!"<<endl;
exit(-1);
}
node *L,*mid,*R; split3(key(x),L,mid,R);
lc(x) = L; rc(x) = R; fa(x) = NULL;
pushup(x);
root = x;
}
void makeroot(Key a){return makeroot(find(a));}
//end: root operation
//start: advance BST operations
int rank(Key a)//smallest to largest
{
node* x = root;
if(!x)return -1;
int ans = 1;
while(x)
{
if(!(a < key(x) || a == key(x)))// a >key(x)
ans += lc(x) ? (sz(lc(x))+1) : 1, x = rc(x);
else x = lc(x);
}
return ans;
}
int rankrev(Key a)
{
node* x = root;
if(!x)return -1;
int ans = 1;
while(x)
{
if(a < key(x))ans += rc(x) ? (sz(rc(x))+1) : 1, x = lc(x);
else x = rc(x);
}
return ans;
}
node* getkth(int k)
{
if(k<1 || k > sz(root))
{
cout<<"Out of range!"<<endl;
return NULL;
}
node *x = root;
while(x)
{
//x->print();
int rs = lc(x) ? sz(lc(x)) : 0;
if(rs < k)
{
k -= rs+1;
if(!k)return x;
x = rc(x);
}
else x = lc(x);
}
return NULL;
}
node* getkthrev(int k)
{
if(k<1 || k > sz(root))
{
cout<<"Out of range!"<<endl;
return NULL;
}
node *x = root;
while(x)
{
int rs = rc(x) ? sz(rc(x)) : 0;
if(rs < k)
{
k -= rs+1;
if(!k)return x;
x = lc(x);
}
else x = rc(x);
}
return NULL;
}
node* Union(node* l, node* r)
{
if(!l)return r;
if(!r)return l;
if(p(l)<p(r))swap(l,r);
node *lt,*rt;
split(r,key(l),lt,rt,true);
lc(l) = Union(lc(l), lt);
rc(l) = Union(rc(l), rt);
return l;
}
//end: advance BST operations
//start: print operation(for debugging)
void print(node* x,int d)
{
if(!x)return ;
pw(d);cout<<"number: " <<x<<endl;
x->print(d);
print(lc(x),d+1);
print(rc(x),d+1);
}
void print()
{
cout<<endl;
print(root,0);
cout<<endl;
}
void destroy(node *x)// destory the structure and free the memory
{
if(!x)return ;
//x->print();
destroy(lc(x));
destroy(rc(x));
delete x;
}
void destroy()
{
destroy(root);
root = NULL;
}
//end: print operation
};
//end Treap
}//end TreapSpace
typedef TreapSpace::treap<int,int,true> Treap;
typedef Treap::node Node;
Treap T;
void work()
{
//cout<<2<<endl;
int i,q,op,x;
scanf("%d",&q);
//printf("%d\n",&q);
for(i=1;i<=q;i++)
{
scanf("%d %d",&op,&x);
switch(op)
{
case 1: {T.insert(x,1);break;}
case 2: {T.erase(x);break;}
case 3: {printf("%d\n",T.rank(x));break;}
case 4: {printf("%d\n",T.getkth(x)->key);break;}
case 5: {printf("%d\n",T.prev(x)->key);break;}
case 6: {printf("%d\n",T.next(x)->key);break;}
default:
cout<<("Invalid Input no in the range of 1-6!\n");
}
//T.print();
}
}
int main()
{
freopen("phs.in", "r", stdin);
freopen("phs.out", "w", stdout);
work();
return 0;
}