|
|
最后奉上我的程序，前前后后3个多小时，丢人
- #include<bits/stdc++.h>
- using namespace std;
- const int inf=99999999;
- const int N=80100;
- struct node
- {
- int val,fa,s[2],sz; ///s0s1左右儿子
- } a[N];
- int p[N],q[N],n,m, 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<<" 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<<" fa ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
- cout<<endl;
- }
- void BSTPr(int rt)
- {
- if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
- cout<<a[rt].val<<' ';
- 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+1;
- }
- int Son(int x)
- {
- int y=a[x].fa;
- return a[y].s[1]==x;
- }
- void R(int x)
- {
- int y=a[x].fa;
- int z=a[y].fa;
- int k=Son(x);
- int v=a[x].s[k^1];
- a[y].s[k]=v,a[v].fa=y;
- a[z].s[Son(y)]=x,a[x].fa=z;
- a[x].s[k^1]=y,a[y].fa=x;
- pushup(y),pushup(x);
- }
- void Splay(int x,int rt=root)
- {
- rt=a[rt].fa;
- int y,z;
- while(a[x].fa!=rt)
- {
- y=a[x].fa,z=a[y].fa;
- if(z!=rt)
- if(Son(x)==Son(y))R(y);
- else R(x);
- R(x);
- }
- if(rt==0)root=x;
- }
- int Ask(int S)
- {
- Splay(S,root);
- int l=a[root].s[0];
- return a[l].sz;
- }
- int Query(int rt, int S) ///在RT子树中找第S小
- {
- int l=a[a[rt].s[0]].sz; /// RT的左儿子下的个数
- if(l+1==S) return a[rt].val;
- if(l+1>S) return Query(a[rt].s[0], S); ///左儿子里去找
- if(l+1<S) return Query(a[rt].s[1], S-(l+1));
- }
- void Top(int S)
- {
- Splay(S,root);
- int x=root;
- int l=a[x].s[0];
- int r=a[x].s[1];///右儿子
- if (r==0) a[x].s[1]=l;
- else
- {
- int p=r;
- ///找最左节点
- while (a[p].s[0]>0) p=a[p].s[0];
- Splay(p,r);
- a[p].s[0]=l;
- a[l].fa=p;
- pushup(p);
- }
- a[x].s[0]=0;
- }
- void Bottom(int S)
- {
- Splay(S,root);
- int x=root;
- int l=a[x].s[0];
- int r=a[x].s[1];
- if (l==0) a[x].s[0]=r;
- else
- {
- int p=l;
- while (a[p].s[1]>0) p=a[p].s[1];
- Splay(p,r);
- a[p].s[1]=r;
- a[r].fa=p;
- pushup(p);
- }
- a[x].s[1]=0;
- }
- int Pre(int S)
- {
- Splay(S,root);
- int l=a[S].s[0], ans=0;
- if (l==0) return 0;
- int p=l;
- while(a[p].s[1]>0) p=a[p].s[1];
- return p;
- }
- int Suc(int S)
- {
- Splay(S,root);
- int r=a[S].s[1];
- if (r==0) return 0;
- int p=r;
- while(a[p].s[0]>0) p=a[p].s[0];
- return p;
- }
- int Build(int l,int r) ///前n个数直接建个满二叉树
- {
- if (l>r) return 0;
- if (l==r)
- {
- a[l].val=p[l];
- a[l].s[0]=a[l].s[1]=0;
- a[l].sz=1;
- return l;
- }
- int m=(l+r)/2;
- a[m].val=p[m];
- int L=a[m].s[0]=Build(l,m-1);
- int R=a[m].s[1]=Build(m+1,r);
- a[L].fa=a[R].fa=m;
- a[m].sz=a[L].sz+a[R].sz+1;
- return m;
- }
- int main()
- {
- cin>>n>>m;
- for (int x,i=1; i<=n; i++)
- {
- cin>>x;
- p[i]=x;
- q[x]=i;
- }
- tot=n;
- root=Build(1,n);
- for (int i=1; i<=n; i++)cout<<q[i]<<' ';
- cout<<endl;
- ///初始建树完毕
- string opt;
- int S,T;
- while(m--)
- {
- cin>>opt;
- if(opt=="Top")
- {
- cin>>S;
- Top(q[S]);
- }
- if(opt=="Bottom")
- {
- cin>>S;
- Bottom(q[S]);
- }
- if(opt=="Insert")
- {
- cin>>S>>T;
- int x;
- if (T==-1)x=Pre(q[S]);
- if (T== 1)x=Suc(q[S]);
- ///这两个交换我曾经搞糊涂了
- swap(q[a[x].val],q[S]);
- swap(a[x].val,a[q[S]].val);
- }
- if(opt=="Ask")
- {
- cin>>S;
- cout<<Ask(q[S])<<endl;
- }
- if(opt=="Query")
- {
- cin>>S;
- cout<<Query(root,S)<<endl;
- }
- }
- return 0;
- }
- /*
- 10 10
- 1 3 2 7 5 8 10 4 9 6
- Query 3
- Top 5
- Ask 6
- Bottom 3
- Ask 3
- Top 6
- Insert 4 -1
- Query 5
- Query 2
- Ask 2
- */
|
|
发表于 2020-4-7 19:15:37
收藏
楼主
