正文 

当前位置： 首页 > java > java教程

bzoj1861:[zjoi2006]book书架

符拉迪沃斯托克 符拉迪沃斯托克     2022-11-09     554

关键词：

BZOJ1861: [Zjoi2006]Book 书架

Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。

她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。

由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。

不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。

当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。

这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。

久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。

于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

Input

第一行有两个数n，m，分别表示书的个数以及命令的条数；

第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；

第三行到m+2行，每行一条命令。命令有5种形式：

1． Top S——表示把编号为S的书房在最上面。

2． Bottom S——表示把编号为S的书房在最下面。

3． Insert S T——T∈-1，0，1，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书；

4． Ask S——询问编号为S的书的上面目前有多少本书。

5． Query S——询问从上面数起的第S本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

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

Sample Output

2
9
9
7
5
3

HINT

数据范围

100%的数据：n,m < = 80000

题解Here！
Splay比较好做，那就一发 Splay 吧。
1. Top 和 Bottom 实质上就是把序列中的一个数放到第一个和最后一个。
具体实现可以把要操作的节点提到根节点，然后把左子树合并到右子树上或把右子树合并到左子树上。

2. Insert操作就是把要操作的节点和前驱后继交换位置，即：把两个点的特征值即编号进行交换。

3. Ask操作询问序列中在此节点前面的数有多少个，提到根节点输出左儿子size就可以了。

4. Query操作就是一个简单的查询序列中第s个数的编号，相当于查询第k大，kth即可。

由于我们需要定位编号为s的节点在树中的位置，所以我使用了 id 数组记录并维护。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 80010
using namespace std;
int n,m,root=1,c=1,id[MAXN];
struct node
	int son[2];
	int f,v,s;
a[MAXN];
inline int read()
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘)if(c==‘-‘)w=-1;c=getchar();
	while(c>=‘0‘&&c<=‘9‘)date=date*10+c-‘0‘;c=getchar();
	return date*w;

inline void clean(int rt)
	a[rt].son[0]=a[rt].son[1]=a[rt].f=a[rt].v=a[rt].s=0;

inline void pushup(int rt)
	if(!rt)return;
	a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;
	id[a[a[rt].son[0]].v]=a[rt].son[0];id[a[a[rt].son[1]].v]=a[rt].son[1];

inline void turn(int rt,int k)
	int x=a[rt].f,y=a[x].f;
	a[x].son[k^1]=a[rt].son[k];
	if(a[rt].son[k])a[a[rt].son[k]].f=x;
	a[rt].f=y;
	if(y)a[y].son[a[y].son[1]==x]=rt;
	a[x].f=rt;
	a[rt].son[k]=x;
	pushup(x);pushup(rt);

void splay(int rt,int ancestry)
	while(a[rt].f!=ancestry)
		int x=a[rt].f,y=a[x].f;
		if(y==ancestry)turn(rt,a[x].son[0]==rt);
		else
			int k=a[y].son[0]==x?1:0;
			if(a[x].son[k]==rt)turn(rt,k^1);turn(rt,k);
			elseturn(x,k);turn(rt,k);
		
	
	if(ancestry==0)root=rt;

int kth(int rt,int x)
	int y=a[rt].son[0];
	if(a[y].s+1==x)return rt;
	else if(x<=a[y].s)return kth(y,x);
	else return kth(a[rt].son[1],x-a[y].s-1);

inline void newnode(int x)
	int rt=c++;
	a[rt].son[0]=a[rt].son[1]=0;
	a[rt].v=x;a[rt].s=1;id[x]=rt;
	if(rt==1)return;
	a[rt-1].son[1]=rt;a[rt].f=rt-1;
	splay(rt,0);

inline void top(int x)
	int rt=id[x];
	splay(rt,0);
	if(!a[rt].son[0])return;
	if(!a[rt].son[1])
		a[rt].son[1]=a[rt].son[0];
		a[rt].son[0]=0;
	
	else
		int y=kth(root,a[a[rt].son[0]].s+2);
		a[a[root].son[0]].f=y;
		a[y].son[0]=a[root].son[0];
		a[root].son[0]=0;
		splay(y,0);
	

inline void bottom(int x)
	int rt=id[x];
	splay(rt,0);
	if(!a[rt].son[1])return;
	if(!a[rt].son[0])
		a[rt].son[0]=a[rt].son[1];
		a[rt].son[1]=0;
	
	else
		int y=kth(root,a[a[rt].son[0]].s);
		a[a[root].son[1]].f=y;
		a[y].son[1]=a[root].son[1];
		a[root].son[1]=0;
		splay(y,0);
	

inline void insert(int x,int y)
	if(!y)return;
	splay(id[x],0);
	int p,q,k=kth(root,a[a[id[x]].son[0]].s+y+1);
	p=a[k].v;q=id[x];
	swap(id[x],id[p]);swap(a[q].v,a[k].v);

inline int ask(int x)
	x=id[x];
	splay(x,0);
	return a[a[x].son[0]].s;

int main()
	char ch[10];
	int x,y;
	n=read();m=read();
	for(int i=1;i<=n;i++)
		x=read();
		newnode(x);
	
	while(m--)
		scanf("%s",ch);x=read();
		switch(ch[0])
			case ‘T‘:top(x);break;
			case ‘B‘:bottom(x);break;
			case ‘I‘:y=read();insert(x,y);break;
			case ‘A‘:printf("%d\n",ask(x));break;
			case ‘Q‘:printf("%d\n",a[kth(root,x)].v);break;
		
	
	return 0;

 

[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在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情

bzoj1861:[zjoi2006]book书架

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

bzoj1861:[zjoi2006]book书架

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

[题解]bzoj1861book书架-splay

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

bzoj1861：[zjoi2006]书架——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1861（题面复制于洛谷）题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一... 查看详情

[bzoj1861][zjoi2006]书架

BZOJLuoguDescription小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 查看详情

bzoj1861:[zjoi2006]book书架（平衡树）(代码片段)

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

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

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

[zjoi2006]书架(代码片段)

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

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

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

「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 查看详情

bzoj1861书架splay版

单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情

bzoj1861书架(代码片段)

题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。操作3，其... 查看详情