首页 > 代码库 > 伸展树复习
伸展树复习
T1 郁闷的出纳员
一个数据结构，支持单点插入、删除几个不一定连续的点、查询k值操作
初做：2017.2.18 time：1268ms memory:3MB
http://www.cnblogs.com/TheRoadToTheGold/p/6412790.html
现在：2017.3.28 time：570ms memory：3MB
初做时直接套模板，删除分5种情况，
本题实际只需3种情况
这一次的查询用递归写的
int query(int now,int k){ int tmp=0; if(ch[now][0]) tmp=sum[ch[now][0]]; if(k<=tmp) return query(ch[now][0],k); if(tmp+cnt[now]>=k) return key[now]; return query(ch[now][1],k-tmp-cnt[now]);}5行开始写的时候每一行都有错误
第二行:tmp=左子树节点个数，遗漏了判断是否有左子树
第三行：当k<=左子树节点个数，漏了等于号
第四行：左子树节点个数+根节点个数（cnt[]数组）>=k，cnt[]和sum[]混了，>写的<
第五行：cnt和sum混了
再就是splay写丑了
贴个精简的：
inline void splay(int x){ for(int fa;fa=f[x];rotate(x)) if(f[fa]) rotate(getson(x)==getson(fa) ? fa:x); root=x; update(x);}
一定要注意update时节点是否有左右孩子
rotate里出现了一个错误：
if(z) ch[z][ch[z][1]==y]=x;
fa[x]=z;这一句是不在if（z）里的
#include<cstdio>#define N 100001using namespace std;int n,limit,gather,root,tot,leave;int sum[N],ch[N][2],fa[N],key[N],cnt[N];void newroot(int x){ sum[++tot]=cnt[tot]=1; key[tot]=x; root=tot;}void newnode(int f,int x){ sum[++tot]=cnt[tot]=1; key[tot]=x; fa[tot]=f; ch[f][x>key[f]]=tot;}void update(int x){ sum[x]=cnt[x]; if(ch[x][0]) sum[x]+=sum[ch[x][0]]; if(ch[x][1]) sum[x]+=sum[ch[x][1]];}void rotate(int x,int kind){ int y=fa[x],z=fa[y]; ch[y][!kind]=ch[x][kind]; fa[ch[y][!kind]]=y; ch[x][kind]=y;fa[y]=x; fa[x]=z; if(z) ch[z][ch[z][1]==y]=x; update(y);}void splay(int x){ while(fa[x]) { int y=fa[x],kind=ch[y][1]==x; if(!fa[y]) rotate(x,!kind); else { int z=ch[fa[y]][1]==y; if(z==kind) { rotate(y,!kind); rotate(x,!kind); } else { rotate(x,!kind); rotate(x,kind); } } } update(x); root=x;}void insert(int x){ if(!root) { newroot(x); return; } int now=root; while(ch[now][x>key[now]]) { if(key[now]==x) { cnt[now]++; update(now); splay(now); return; } now=ch[now][x>key[now]]; } if(key[now]==x) { cnt[now]++; update(now); splay(now); return; } newnode(now,x); update(now); splay(tot);}void cut_lch(){ int tmp=ch[root][0]; if(tmp) leave+=sum[tmp]; fa[tmp]=0; ch[root][0]=0; update(root);}void cut(){ if(cnt[root]>1) { cnt[root]--; update(root); return; } if(!ch[root][1]) { root=0; gather=0; return; } int tmp=ch[root][1]; fa[tmp]=0; ch[root][1]=0; root=tmp;}int query(int now,int k){ int tmp=0; if(ch[now][0]) tmp=sum[ch[now][0]]; if(k<=tmp) return query(ch[now][0],k); if(tmp+cnt[now]>=k) return key[now]; return query(ch[now][1],k-tmp-cnt[now]);}int main(){ freopen("cashier.in","r",stdin); freopen("cashier.out","w",stdout); scanf("%d%d",&n,&limit); char ch[1];int x; while(n--) { scanf("%s%d",ch,&x); switch(ch[0]) { case ‘I‘: if(x<limit) continue; insert(x-gather); break; case ‘A‘: gather+=x; break; case ‘S‘: gather-=x; insert(limit-gather); cut_lch(); cut(); break; case ‘F‘: if(x>sum[root]) printf("-1\n"); else printf("%d\n",query(root,sum[root]-x+1)+gather); } } printf("%d",leave);}
T2 反转卡片
http://www.cnblogs.com/TheRoadToTheGold/p/6414979.html
初做：2017.2.19 现在：2017.3.28
3个小时
这个题使splay中的节点编号与节点在序列中的顺序保持一致，然后splay的中序遍历就是卡片顺序。
所以第i张卡片相当于splay中排名为i的节点，而且不需要在splay中存储权值，即卡片上的数字
所以以前认为将卡片编号作为权值建splay是错误的
#include<cstdio>#include<algorithm>#define N 300010using namespace std;int n,num[N],root;int fa[N],ch[N][2],sum[N];bool tag[N];void update(int x){ sum[x]=1+sum[ch[x][0]]+sum[ch[x][1]];}void build(int l,int r,int f){ if(l>r) return; int mid=l+r>>1; fa[mid]=f;sum[mid]=1; ch[f][mid>f]=mid; build(l,mid-1,mid); build(mid+1,r,mid); update(mid);}int getson(int x){ return ch[fa[x]][1]==x;}void rotate(int x,int & goal){ int y=fa[x],z=fa[y],kind=getson(x); if(y==goal) goal=x; else ch[z][ch[z][1]==y]=x; ch[y][kind]=ch[x][!kind]; fa[ch[y][kind]]=y; ch[x][!kind]=y; fa[y]=x; fa[x]=z; update(y);}void down(int x){ tag[x]^=1; if(ch[x][0]) tag[ch[x][0]]^=1; if(ch[x][1]) tag[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]);}void splay(int x,int & goal){ while(x!=goal) { if(tag[fa[fa[x]]]) down(fa[fa[x]]); if(tag[fa[x]]) down(fa[x]); if(tag[x]) down(x); int y=fa[x]; if(y!=goal) { if(getson(y)==getson(x)) rotate(y,goal); else rotate(x,goal); } rotate(x,goal); } update(x);}int find(int now,int x){ if(tag[now]) down(now); int tmp=0; if(ch[now][0]) tmp=sum[ch[now][0]]; if(x<=tmp) return find(ch[now][0],x); if(tmp+1>=x) return now; return find(ch[now][1],x-tmp-1);}void rever(int l,int r){ int x=find(root,l-1),y=find(root,r+1); splay(x,root);splay(y,ch[x][1]); tag[ch[y][0]]^=1;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&num[i+1]); build(1,n+2,0); root=(n+3)/2; int maxn=100000,id,r,ans=0; while(maxn--) { id=find(root,2); r=num[id]; if(r==1) { printf("%d",100000-maxn-1); return 0; } rever(2,r+1); } printf("-1");}
列举代码中好几个错误：
①、答案的输出
if(r==1){ printf("%d",100000-maxn-1); return 0;}
而不是 100000-maxn
因为开头写的 while(maxn--)
判断完maxn为true后，减1，输出里的maxn相对于while里已经减了1，所以应该是100000-（maxn+1）
②、rever函数中，打翻转标记应该是tag[ch[y][0]]^=1;
而不是tag[ch[y][0]]=1
③、find函数里now和x混了，属于不过脑子的错误
④、splay里用了这个
inline void splay(int x){ for(int fa;fa=f[x];rotate(x)) if(f[fa]) rotate(getson(x)==getson(fa) ? fa:x); root=x; update(x);}
上面的判断标准是f[fa]为true，因为根节点的父节点是0
这个题是将点转到指定位置，所以判断标准是父节点是否是目标位置
修改上面的代码改了好久就是不过
所以，若是将点转到指定位置，干脆用这个
void splay(int x,int & goal){ while(x!=goal) { if(tag[fa[fa[x]]]) down(fa[fa[x]]); if(tag[fa[x]]) down(fa[x]); if(tag[x]) down(x); int y=fa[x]; if(y!=goal) { if(getson(y)==getson(x)) rotate(y,goal); else rotate(x,goal); } rotate(x,goal); } update(x);}
原来写的代码没有下传标记A了，很神奇
⑤、rotate 里
if(y==goal) goal=x; else ch[z][ch[z][1]==y]=x;
而不是
if（z）ch[z][ch[z][1]==y]=x;
⑥、build里 update（mid）而不是update（f）
还有一点：这里所有有关父节点与子节点的操作，都不需要判断是否有子节点
why？
伸展树复习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。