题目链接: https://www.luogu.org/problemnew/show/P3369
修改了一下之前的模板, 支持重复数值的存储
- #include<bits/stdc++.h>
- using namespace std;
- struct node
- {
- int val;
- node *father;
- node *son[2];
- int cnt;
- int siz;
- } tree[100005],*root;
- inline void init(node *p,int val=0)
- {
- p->father=NULL;
- p->son[0]=p->son[1]=NULL;
- p->val=val;
- p->siz=1;
- p->cnt=1;
- }
- inline int siz(node *t)
- {
- return t == NULL ? 0 : t->siz;
- }
- inline void update(node *t)//rotate 与 erase 操作时需更新
- {
- t->siz = t->cnt;
- t->siz += siz(t->son[0]);
- t->siz += siz(t->son[1]);
- }
- inline bool son(node *f, node *s)
- {
- return f->son[1] == s;
- }
- inline void rotate(node *t)
- {
- node *f = t->father;
- node *g = f->father;
- bool a = son(f, t), b = !a;
- f->son[a] = t->son[b];
- if (t->son[b] != NULL)
- t->son[b]->father = f;
- t->son[b] = f;
- f->father = t;
- t->father = g;
- if (g != NULL)
- g->son[son(g, f)] = t;
- else
- root = t;
- update(t);
- update(f);
- }
- inline void splay(node *t, node *p)
- {
- while (t->father != p)
- {
- node *f = t->father;
- node *g = f->father;
- if (g == p)
- rotate(t);
- else
- {
- if (son(g, f) ^ son(f, t))
- rotate(t), rotate(t);
- else
- rotate(f), rotate(t);
- }
- }
- }
- inline void insert(node* p)
- {
- if (root == NULL)
- {
- root = p;
- return;
- }
- for(node* t=root; t; t = t->son[t->val <p->val])
- {
- t->siz++;
- if(t->val==p->val)
- {
- t->cnt++;
- splay(t,NULL);
- return;
- }
- if(t->son[t->val <p->val]==NULL)
- {
- t->son[t->val <p->val]=p;
- p->father=t;
- splay(p,NULL);
- return;
- }
- }
- }
- inline void erase(node *t)
- {
- splay(t,NULL);
- if (t->son[0] == NULL)
- {
- root = t->son[1];
- if (root != NULL)
- root->father = NULL;
- }
- else
- {
- node *p = t->son[0];
- while (p->son[1] != NULL)
- p = p->son[1];
- splay(p, t);
- root = p;
- root->father = NULL;
- p->son[1] = t->son[1];
- if (p->son[1] != NULL)
- p->son[1]->father = p;
- update(p);
- }
- }
- int n,m;
- bool flag;
- inline node* findx(int kth)
- {
- node* p=root;
- while(1)
- {
- if(kth<=siz(p->son[0])) p=p->son[0];
- else
- {
- kth-=siz(p->son[0])+p->cnt;
- if(kth<=0) return p;
- p=p->son[1];
- }
- }
- }
- inline node* findkth(int x)
- {
- node* p=root;
- while(1)
- {
- if(p==NULL) return NULL;
- if(p->val==x) return p;
- p=p->son[p -> val <x];
- }
- }
- int main()
- {
- int m;
- scanf("%d",&m);
- int tot=0;
- for(int i=1;i<=m;i++)
- {
- int op;
- scanf("%d",&op);
- if(op==1)
- {
- int x;
- scanf("%d",&x);
- init(&tree[++tot],x);
- insert(&tree[tot]);
- }
- if(op==2)
- {
- int x;
- scanf("%d",&x);
- node* tmp=findkth(x);
- if(tmp!=NULL)
- {
- tmp->cnt--;
- if(!tmp->cnt)
- erase(tmp);
- else
- splay(tmp,NULL);
- }
- }
- if(op==3)
- {
- int x;
- scanf("%d",&x);
- node* tmp=findkth(x);
- splay(tmp,NULL);
- if(tmp->son[0]==NULL)
- puts("1");
- else
- printf("%d\n",tmp->son[0]->siz+1);
- }
- if(op==4)
- {
- int kth;
- scanf("%d",&kth);
- node *tmp=findx(kth);
- if(tmp!=NULL) printf("%d\n",tmp->val);
- }
- if(op==5)
- {
- int x;
- scanf("%d",&x);
- node* p=root;
- int tmp;
- while(1)
- {
- if(p==NULL) break;
- if(p->val>=x)
- p=p->son[0];
- else
- {
- tmp=p->val;
- p=p->son[1];
- }
- }
- printf("%d\n",tmp);
- }
- if(op==6)
- {
- int x;
- scanf("%d",&x);
- node* p=root;
- int tmp;
- while(1)
- {
- if(p==NULL) break;
- if(p->val<=x)
- p=p->son[1];
- else
- {
- tmp=p->val;
- p=p->son[0];
- }
- }
- printf("%d\n",tmp);
- }
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-2963959.html