正文

解题：zjoi2006书架(代码片段)

ydnhaha  ydnhaha  2023-01-20  339

关键词：

学习了如何在维护序列的平衡树上查找某个数：按初始的顺序定个权值，然后每次找那个权值的DFS序即可。具体实现就是不停往上跳，然后是父亲的右儿子就加上父亲的左儿子，剩下的就是继续熟悉无旋树堆

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=100005;
  6 int num[N],val[N],siz[N],anc[N],son[N][2],rnk[N];
  7 int n,m,w,x,y,z,rd,re,tot,pos,root; char ch[10];
  8 void Pushup(int nde)
  9 
 10     siz[nde]=siz[son[nde][0]]+siz[son[nde][1]]+1;
 11     if(son[nde][0]) anc[son[nde][0]]=nde;
 12     if(son[nde][1]) anc[son[nde][1]]=nde;
 13 
 14 int Create(int tsk)
 15 
 16     siz[++tot]=1;
 17     val[tot]=tsk;
 18     num[tsk]=tot;
 19     rnk[tot]=rand();
 20     return tot;
 21 
 22 int Merge(int x,int y)
 23 
 24     if(!x||!y) return x+y;
 25     else if(rnk[x]<=rnk[y])
 26     
 27         son[x][1]=Merge(son[x][1],y);
 28         Pushup(x); return x;    
 29      
 30     else 
 31     
 32         son[y][0]=Merge(x,son[y][0]);
 33         Pushup(y); return y;
 34     
 35 
 36 void Split(int nde,int &x,int &y,int tsk)
 37 
 38     if(!nde) x=y=0;
 39     else
 40     
 41         if(siz[son[nde][0]]<tsk)
 42             x=nde,Split(son[nde][1],son[nde][1],y,tsk-siz[son[nde][0]]-1);
 43         else 
 44             y=nde,Split(son[nde][0],x,son[nde][0],tsk);
 45         Pushup(nde); 
 46     
 47 
 48 int Query(int nde)
 49 
 50     int ret=siz[son[nde][0]]+1;
 51     while(anc[nde]) 
 52         if(nde==son[anc[nde]][1])
 53         ret+=siz[son[anc[nde]][0]]+1;
 54         nde=anc[nde];
 55     
 56     return ret;
 57 
 58 void DFS(int nde)
 59 
 60     if(son[nde][0]) DFS(son[nde][0]);
 61     printf("->%d",val[nde]);
 62     if(son[nde][1]) DFS(son[nde][1]);
 63 
 64 int main()
 65 
 66     srand(20020513);
 67     scanf("%d%d",&n,&m);
 68     for(int i=1;i<=n;i++)
 69         scanf("%d",&rd),root=Merge(root,Create(rd));
 70     while(m--)
 71     
 72         scanf("%s%d",ch,&rd),pos=Query(num[rd]); 
 73         if(ch[0]==‘T‘) 
 74         
 75             Split(root,x,z,pos),Split(x,x,y,pos-1);
 76             root=Merge(Merge(y,x),z);
 77         
 78         else if(ch[0]==‘B‘)
 79         
 80             Split(root,x,z,pos),Split(x,x,y,pos-1);
 81             root=Merge(Merge(x,z),y);
 82         
 83         else if(ch[0]==‘I‘)
 84         
 85             scanf("%d",&re);
 86             if(re==-1)
 87             
 88                 Split(root,w,z,pos),Split(w,w,y,pos-1); 
 89                 Split(w,w,x,pos-2); root=Merge(Merge(Merge(w,y),x),z);
 90             
 91             else if(re==1)
 92             
 93                 Split(root,y,z,pos+1),Split(y,x,y,pos);
 94                 Split(x,w,x,pos-1); root=Merge(Merge(Merge(w,y),x),z);
 95             
 96         
 97         else if(ch[0]==‘A‘)
 98             printf("%d
",pos-1);
 99         else
100         
101             Split(root,x,z,rd),Split(x,x,y,rd-1);
102             printf("%d
",val[y]); 
103             root=Merge(Merge(x,y),z);
104         
105     
106     return 0;
107

View Code

[zjoi2006]书架(代码片段)

[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树时间复杂度：O(MlogN)[代码] &n 查看详情

p2596[zjoi2006]书架(代码片段)

\\(\\colorpurple\\textP2596[ZJOI2006]书架\\)解题方法考虑使用\\(\\textFHQ\\)平衡树，我们只使用编号，而不使用权值，平衡树上的先序遍历即为书的放置顺序。\\(\\textQuery\\)：这是最简单的操作，直接查询即可。\\(\\textAsk\\)：本题的核心，... 查看详情

[zjoi2006]书架(代码片段)

[ZJOI2006]书架题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这... 查看详情

「luogu2596」[zjoi2006]书架(代码片段)

用平衡树维护每本书的位置1#include<bits/stdc++.h>2usingnamespacestd;3constintN=80010;4intn,m,maxpos,minpos,book[N<<2],bookpos[N];5introot,fa[N<<2],ch[N<<2][2],siz[N<<2],pos[N<<2 查看详情

zjoi2006书架(代码片段)

传送门这道题与普通的(splay)不大相同，别的都是以权值来排序，但这道题是以位置进行排序的，也就是对于一个节点，它的左子树中的节点都在它的上面，右子树中的节点都在他的下面。这个比较独特的一点在于建树，这次不... 查看详情

[zjoi2006]书架(代码片段)

题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情

[zjoi2006]book书架(代码片段)

DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情

1861.[zjoi2006]书架平衡树-splay(代码片段)

Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情

洛谷p2596[zjoi2006]书架splay(代码片段)

[zjoi2006]book书架

pre.cjk{font-family:"DroidSansFallback",monospace}p{margin-bottom:0.25cm;line-height:120%}a:link{}1861:[Zjoi2006]Book书架TimeLimit:4Sec MemoryLimit:64MBSubmit:1581 Solved:884[Submi 查看详情

bzoj1861[zjoi2006]book书架——splay

【题目分析】模板题目。首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情

bzoj1861:[zjoi2006]book书架（splay）

1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1453 Solved: 822[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到查看详情

[luogu2596]zjoi2006书架

[Luogu2596]ZJOI2006书架<题目链接>第一次指针写FHQ_Treap（省选噩梦数据结构）AC啦！省选试机写它，紧张过度失败了。省选Day1考场写它，写挂了。省选Day1当晚认真复习它，结果Day2并不考。于是省选后用指针写出来了，开心qwq。... 查看详情

题解[zjoi2006]书架（splay）

懒得复制，戳我戳我Solution:还是一个\(Splay\)，我们只用多存一个值\(rad\)来维护二叉树，然后用数组存下每个书对应的值是多少\(Top\)操作，我是把\(s\)旋转到根节点，然后删除，将\(s\)对应的\(rad\)值调至最小，然后插入就可以\(Bot... 查看详情

[zjoi2006]书架（权值splay）(代码片段)

[ZJOI2006]书架（luogu）Description题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿... 查看详情

bzoj1861:[zjoi2006]book书架

BZOJ1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本... 查看详情

[bzoj1861][zjoi2006]book书架

[BZOJ1861][Zjoi2006]Book书架试题描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一... 查看详情

bzoj1861[zjoi2006]book书架

1#include<bits/stdc++.h>2usingnamespacestd;3constintN=8e4+5;4constintinf=1e9;5intfa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;6voidupdate(intx)7{8size[x]=size[c[x][0]]+size[c[x][1]]+1;9}10voidr 查看详情