P1097 统计数字 - 华师一附中OI组

#include <iostream>
using namespace std;
struct BSTnode
{
int data;
int cnt;
BSTnode *l,*r;
} *T;
void BSTins(BSTnode *&bst, int x) ///把x插入到bst树中
{
if (bst==NULL) ///
{
BSTnode *p=new BSTnode;
p->data=x;
p->cnt=1;
p->l=p->r=NULL;
bst=p;
}
else if (x<bst->data) BSTins(bst->l,x);
else if (x>bst->data) BSTins(bst->r,x);
else if (x==bst->data) bst->cnt++;
}
void inorder(BSTnode *bst)
{
if (bst!=NULL)
{
inorder(bst->l);
cout<<bst->data<<' ';///<<bst->cnt<<'\t';
inorder(bst->r);
}
}
BSTnode * BSTfind(BSTnode * bst, int x)
{
if (bst==NULL) return NULL;
else if (bst->data==x) return bst;
else if (bst->data>x) return BSTfind(bst->l, x);
else if (bst->data<x) return BSTfind(bst->r, x);
}
bool BSTdel(BSTnode * & bst,int x)
{
if (bst==NULL) return 0; ///没有这个数，删除未成功
else if (bst->data>x) return BSTdel(bst->l,x);
else if (bst->data<x) return BSTdel(bst->r,x);
else if (bst->cnt>1) {bst->cnt--;return 1;} ///存在这个数，减1
{
///BSTnode *p=bst;
if (bst->l==NULL) ///没有左子树就直接把右子树接上来
{
bst=bst->r;
///del(p);
return 1;
}
else if (bst->r==NULL) ///没有右子树就直接把左子树接上来
{
bst=bst->l;
///del(p);
return 1;
}
else
{
if (bst->l->r==NULL) //左儿子没有右儿子
{
bst->data=bst->l->data;
bst->cnt=bst->l->cnt;
return BSTdel(bst->l,bst->l->data);
}
else
{ /// 这里有问题没写好
BSTnode *p1=bst, *p2=bst->l;
while (p2->r==NULL)
{
p1=p2;
p2=p2->r;
}
bst->data=p2->data;
bst->cnt=p2->cnt;
return BSTdel(p1->r,p2->data);
}
}
}
}
int main()
{
int x;
cin>>x;
while (x>0)
{
BSTins(T,x);
cin>>x;
}
inorder(T);cout<<endl;
cin>>x;
while (x>0) /// 删除
{
BSTdel(T,x);
inorder(T);
cout<<endl;
cin>>x;
}
return 0;
}
/*
50 25 75 18 38 66 80 10 16 26 40 62 68 79 90 9 12 15 30 42 93 8 14 41 43 95 6 44 94 99 5 7 0
*/

复制代码

#include<bits/stdc++.h>
using namespace std;
const int SIZE=1e6+9;
const int inf=1<<30;
struct Treap{int l,r,val,dat,cnt,size;}a[SIZE];
int tot,root,n;
inline int New(int val){
a[++tot].val=val;
a[tot].dat=rand();
a[tot].cnt=a[tot].size=1;
return tot;
}
inline void Update(int p){
a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
}
inline void Build(){
New(-inf),New(inf);
root=1,a[1].r=2;
Update(root);
}
inline void zig(int &p){
int q=a[p].l;
a[p].l=a[q].r,a[q].r=p,p=q;
Update(a[p].r),Update(p);
}
inline void zag(int &p){
int q=a[p].r;
a[p].r=a[q].l,a[q].l=p,p=q;
Update(a[p].l),Update(p);
}
void Insert(int &p,int val){
if(p==0) return p=New(val),void();
if(val==a[p].val) return a[p].cnt++,Update(p),void();
if(val<a[p].val){
Insert(a[p].l,val);
if(a[p].dat<a[a[p].l].dat) zig(p);
}
else{
Insert(a[p].r,val);
if(a[p].dat<a[a[p].r].dat) zag(p);
}
Update(p);
}
inline int GetPre(int val){
int ans=1;
int p=root;
while(p){
if(val==a[p].val){
if(a[p].l>0){
p=a[p].l;
while(a[p].r>0) p=a[p].r;
ans=p;
}
break;
}
if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
p=(val<a[p].val)?a[p].l:a[p].r;
}
return a[ans].val;
}
inline int GetNext(int val){
int ans=2;
int p=root;
while(p){
if(val==a[p].val){
if(a[p].r>0){
p=a[p].r;
while(a[p].l>0) p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
p=(val<a[p].val)?a[p].l:a[p].r;
}
return a[ans].val;
}
int GetRankByVal(int p,int val){
if(p==0) return 0;
if(val==a[p].val) return a[a[p].l].size+1;
if(val<a[p].val) return GetRankByVal(a[p].l,val);
return GetRankByVal(a[p].r,val)+a[a[p].l].size+a[p].cnt;
}
int GetValByRank(int p,int rank){
if(p==0) return inf;
if(a[a[p].l].size>=rank) return GetValByRank(a[p].l,rank);
if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
return GetValByRank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
void Remove(int &p,int val){
if(p==0) return;
if(val==a[p].val){
if(a[p].cnt>1){
a[p].cnt--,Update(p);
return;
}
if(a[p].l||a[p].r){
if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat) zig(p),Remove(a[p].r,val);
else zag(p),Remove(a[p].l,val);
Update(p);
}
else p=0;
return;
}
(val<a[p].val)?Remove(a[p].l,val):Remove(a[p].r,val);
Update(p);
}
void middle_traval(int x){
if(x<=0||x>1500000000) return;
cout<<a[x].val<<" "<<a[x].cnt<<'\n';
middle_traval(a[x].l);
middle_traval(a[x].r);
}
int main(){
srand((unsigned)time(NULL));
ios::sync_with_stdio(0);
Build();
cin>>n;
for(int i=1;i<=n;++i){
int x;
cin>>x;
Insert(root,x);
}
Remove(root,-inf),Remove(root,inf);
middle_traval(root);
// while(n--){
// int opt,x;
// cin>>opt>>x;
// if(opt==1) Insert(root,x);
// else if(opt==2) Remove(root,x);
// else if(opt==3) cout<<GetRankByVal(root,x)-1<<'\n';
// else if(opt==4) cout<<GetValByRank(root,x+1)<<'\n';
// else if(opt==5) cout<<GetPre(x)<<'\n';
// else if(opt==6) cout<<GetNext(x)<<'\n';
// }
return 0;
}

复制代码

#include<bits/stdc++.h>
using namespace std;
const int inf=9999999;
const int N=100100;
struct node
{
int val,cnt;
int fa,s[2],sz; ///s0s1左右儿子
} a[N];
int n, tot, root;
void ArrayPr() /// 调试监视使用
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<"cnt ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" sz ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
cout<<endl;
}
void BSTPr(int rt) ///中序输出以rt为根的BST
{
if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
if (a[rt].s[1]>0) BSTPr(a[rt].s[1]);
}
void pushup(int rt) ///类似线段树网上调整
{
int l=a[rt].s[0], r=a[rt].s[1];
a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
}
void LR(int rt)/// 左旋因为有了fa，所以不需要传地址但是也多了修改fa指针的操作
{
///cout<<"L\n";
int x=a[rt].fa; ///x是rt的爸爸
int y=a[x].fa;///y是x的爸爸 rt的爷爷
int l=a[rt].s[0];
a[x].s[1]=l;///rt的左儿子挂给x当右儿子（本来右儿子是rt）
if(l!=0) a[l].fa=x; //这个要注意空节点没有fa
a[rt].fa=y; //rt取代了他的爸爸x
a[rt].s[0]=x;//rt的原父节点x成为rt 的左儿子
if(y!=0)
{
if(x==a[y].s[0])
a[y].s[0]=rt;
else a[y].s[1]=rt;
}
a[x].fa=rt;
pushup(x),pushup(rt);
}
void RR(int rt) /// 同上右旋
{
///cout<<"R\n";
int x=a[rt].fa; ///x是rt的爸爸
int y=a[x].fa;///y是x的爸爸 rt的爷爷
int r=a[x].s[0]=a[rt].s[1];
if(r!=0) a[r].fa=x;
a[rt].fa=y; //rt取代了他的爸爸x
a[rt].s[1]=x;
if(y!=0)
{
if(x==a[y].s[0])
a[y].s[0]=rt;
else a[y].s[1]=rt;
}
a[x].fa=rt; pushup(x),pushup(rt);
}
void splay(int rt)//伸展操作: 6种情况
{
int x,y;
while(a[rt].fa!=0)//反复进行旋转，直至将x节点调整至根部为止
{
x=a[rt].fa;///rt的爸爸
y=a[x].fa;
if(y==0)//在x为根的情况下，若x在左儿子位置，则右旋；否则左旋
{
if(rt==a[x].s[0]) RR(rt);
else LR(rt);
break;
}
if(rt==a[x].s[0])//在x位于左位置的情况下，若x的父节点位于左位置，则分别
//以x的父节点和x为基准两次右旋；否则以x为基准右旋和左旋
{
if(x==a[y].s[0]) ///LLL
{
RR(x);
RR(rt);
}
else ///LLR
{
RR(rt);
LR(rt);
}
}
else
{
if(x==a[y].s[1]) ///RRR
{
LR(x);
LR(rt);
}
else
{
LR(rt);
RR(rt);
}
}
}
root=rt;//新根
//cout<<rt<<endl;
}
void Ins(int rt, int x) /// 在rt子树中插入x
{
if(rt==0) /// 新树
{
tot=root=1;
a[1].fa=a[1].s[0]=a[1].s[1]=0;
a[1].val=x;
a[1].cnt=1;
}
else if(a[rt].val==x) a[rt].cnt++;
else if(a[rt].val<x)
{
if (a[rt].s[1]==0)
{
a[rt].s[1]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=1;
splay(tot);
}
else
Ins(a[rt].s[1],x);
}
else if(a[rt].val>x)
{
if (a[rt].s[0]==0)
{
a[rt].s[0]=++tot;
a[tot].s[0]=a[tot].s[1]=0;
a[tot].val=x;
a[tot].fa=rt;
a[tot].cnt=1;
splay(tot);
}
else
Ins(a[rt].s[0], x);
}
}
int main()
{
cin>>n;
while(n--)
{
int x;
cin>>x;
Ins(root,x);
}
BSTPr(root);
return 0;
}

复制代码