关键词：
[Luogu 2596] ZJOI2006 书架
第一次指针写 FHQ_Treap（省选噩梦数据结构）AC 啦！
省选试机写它，紧张过度失败了。
省选 Day 1 考场写它，写挂了。
省选 Day 1 当晚认真复习它，结果 Day 2 并不考。
于是省选后用指针写出来了，开心qwq。
这个题嘛，记录一下每个点对应的指针，顺便维护一下父节点，每次需要的时候，就可以一路向上找到这个点的位置。
就这么简单的呀qwq
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <stack>
using std::stack;
const int MAXN=80010;
int n,m,pos[MAXN];
class FHQ_Treap
public:
FHQ_Treap(void)
srand(19260817);
rt=nullptr;
~FHQ_Treap(void)
delete rt;
void Init(void)
Build(rt);
void Top(void)
int x;
Node *l,*r,*t;
scanf("%d",&x);
x=Rank(pos[x]);
Split(rt,x-1,l,r),Split(r,1,t,r),Merge(l,t,l),Merge(rt,l,r);
void Bottom(void)
int x;
Node *l,*r,*t;
scanf("%d",&x);
x=Rank(pos[x]);
Split(rt,x-1,l,r),Split(r,1,t,r),Merge(r,r,t),Merge(rt,l,r);
void Insert(void)
int x,k;
scanf("%d %d",&x,&k);
if(!k)
return;
Node *l,*r,*p,*q;
x=Rank(pos[x]);
if(k==-1)
Split(rt,x-2,l,r);
else
Split(rt,x-1,l,r);
Split(r,1,p,r),Split(r,1,q,r),Merge(l,l,q),Merge(r,p,r),Merge(rt,l,r);
void Ask(void)
int x;
scanf("%d",&x);
printf("%d\n",Rank(pos[x])-1);
void Query(void)
int x;
Node *l,*r,*t;
scanf("%d",&x);
Split(rt,x-1,l,r),Split(r,1,t,r);
printf("%d\n",t->v);
Merge(l,l,t),Merge(rt,l,r);
private:
struct Node
int v,p,num,size;
Node *ft,*c[2];
Node(int v=0,int p=0,int num=0,int size=0):v(v),p(p),num(num),size(size)
ft=c[0]=c[1]=nullptr;
~Node(void)
if(c[0]!=nullptr)
delete c[0];
if(c[1]!=nullptr)
delete c[1];
*rt,*pos[MAXN];
void Update(Node *i)
i->size=1,pos[i->v]=i;
if(i->c[0]!=nullptr)
i->size+=i->c[0]->size;
i->c[0]->ft=i;
if(i->c[1]!=nullptr)
i->size+=i->c[1]->size;
i->c[1]->ft=i;
void Build(Node *&k)
stack<Node *> st;
for(int i=1,t;i<=n;++i)
scanf("%d",&t);
Node *x=new Node(t,rand(),i,1);
pos[t]=x,k=nullptr;
while(!st.empty() && x->p>st.top()->p)
Update(k=st.top()),st.pop();
if(!st.empty())
st.top()->c[1]=x;
x->c[0]=k,st.push(x);
while(!st.empty())
Update(k=st.top()),st.pop();
void Split(Node *i,int x,Node *&l,Node *&r)
if(i==nullptr)
l=r=nullptr;
return;
int t=(i->c[0]!=nullptr ? i->c[0]->size : 0)+1;
if(x<t)
Split((r=i)->c[0],x,l,i->c[0]);
else
Split((l=i)->c[1],x-t,i->c[1],r);
Update(i);
void Merge(Node *&i,Node *l,Node *r)
if(l==nullptr || r==nullptr)
i=l!=nullptr ? l : r;
return;
if(l->p>r->p)
Merge((i=l)->c[1],l->c[1],r);
else
Merge((i=r)->c[0],l,r->c[0]);
Update(i);
int Rank(Node *i)
int ans=(i->c[0]!=nullptr ? i->c[0]->size : 0)+1;
while(i->ft!=nullptr)
if(i==i->ft->c[1])
ans+=(i->ft->c[0]!=nullptr ? i->ft->c[0]->size : 0)+1;
i=i->ft;
return ans;
*T=new FHQ_Treap;
int main(int argc,char *argv[])
scanf("%d %d",&n,&m);
T->Init();
for(int i=1;i<=m;++i)
char str[10];
scanf("\n%s",str);
switch(str[0])
case ‘T‘:
T->Top();
break;
case ‘B‘:
T->Bottom();
break;
case ‘I‘:
T->Insert();
break;
case ‘A‘:
T->Ask();
break;
case ‘Q‘:
T->Query();
break;
delete T;
return 0;
谢谢阅读。
p2596[zjoi2006]书架(代码片段)
\\(\\colorpurple\\textP2596[ZJOI2006]书架\\)解题方法考虑使用\\(\\textFHQ\\)平衡树，我们只使用编号，而不使用权值，平衡树上的先序遍历即为书的放置顺序。\\(\\textQuery\\)：这是最简单的操作，直接查询即可。\\(\\textAsk\\)：本题的核心，... 查看详情
洛谷p2596[zjoi2006]书架splay(代码片段)
题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
[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 查看详情
[zjoi2006]书架(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树 时间复杂度：O(MlogN)[代码] &n 查看详情
bzoj1861:[zjoi2006]book书架（splay）
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1453 Solved: 822[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
[zjoi2006]书架(代码片段)
[ZJOI2006]书架题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这... 查看详情
题解[zjoi2006]书架（splay）
懒得复制，戳我戳我Solution:还是一个\(Splay\)，我们只用多存一个值\(rad\)来维护二叉树，然后用数组存下每个书对应的值是多少\(Top\)操作，我是把\(s\)旋转到根节点，然后删除，将\(s\)对应的\(rad\)值调至最小，然后插入就可以\(Bot... 查看详情
解题：zjoi2006书架(代码片段)
题面学习了如何在维护序列的平衡树上查找某个数：按初始的顺序定个权值，然后每次找那个权值的DFS序即可。具体实现就是不停往上跳，然后是父亲的右儿子就加上父亲的左儿子，剩下的就是继续熟悉无旋树堆1#include<cstdio&g... 查看详情
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 查看详情
bzoj1861:[zjoi2006]book书架
这题想写三次了。结果前两次太困╯﹏╰没写成，大数据结构题就是烦人啊。没什么值得注意的，就按题意一步步来吧。（写了map表示对应树上位置，担心编号大爆掉，不加好像也没啥关系）#include<cstdio>#include<iostream>#i... 查看详情
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书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情
zjoi2006书架(代码片段)
传送门这道题与普通的(splay)不大相同，别的都是以权值来排序，但这道题是以位置进行排序的，也就是对于一个节点，它的左子树中的节点都在它的上面，右子树中的节点都在他的下面。这个比较独特的一点在于建树，这次不... 查看详情
[bzoj1861][zjoi2006]书架
BZOJLuoguDescription小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太... 查看详情
[zjoi2006]书架(代码片段)
题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
bzoj1861：[zjoi2006]书架——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1861（题面复制于洛谷）题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一... 查看详情