列表

详情

NC20463. [ZJOI2006]BOOK 书架

描述

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 
小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 
当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：
(1)编号为X的书在书柜的什么位置；
(2)从上到下第i本书的编号是多少。

输入描述

第一行有两个数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本书的编号。

输出描述

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

示例1

输入: 

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

输出: 

2
9
9
7
5
3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 101ms, 内存消耗: 2792K, 提交时间: 2020-04-01 19:29:13 

#include<bits/stdc++.h>
#define lson t[x].son[0]
#define rson t[x].son[1]
using namespace std;
const int MX=1e5+9;
const int head=1e5+1;
const int tail=1e5+2;
struct node{
    int siz,val,fa;
    int son[2];
}t[MX];
int root,sz=0,pos[MX];
int n,m,val[MX];
char s[MX];

int get(int x){
    return t[t[x].fa].son[1]==x;
}

void pushup(int x){
    t[x].siz=1;
    if( lson ) t[x].siz+=t[lson].siz;
    if( rson ) t[x].siz+=t[rson].siz;
}

void rotate(int x){
    int f=t[x].fa,ff=t[f].fa,kx=get(x),kf=get(f);
    t[ff].son[kf]=x,t[x].fa=ff;
    t[f].son[kx]=t[x].son[!kx],t[t[x].son[!kx]].fa=f;
    t[x].son[!kx]=f,t[f].fa=x;
    pushup(f),pushup(x);
}

void splay(int rt,int x){
    while( t[x].fa!=rt ){
        int f=t[x].fa,ff=t[f].fa;
        if( ff!=rt ){
            if( get(x)==get(f) )
                rotate(f);
            else
                rotate(x);
        }
        rotate(x);
    }
    if( rt==0 )
        root=x;
}

int build(int l,int r,int fa){
    if( l>r )
        return 0;
    int mid=(l+r)>>1;
    int x=++sz;
    t[x].val=val[mid];
    pos[t[x].val]=x;
    t[x].fa=fa;
    lson=rson=0;
    lson=build(l,mid-1,x);
    rson=build(mid+1,r,x);
    pushup(x);   // 这个不可以忘记
    return x;
}

int las(int x){
    splay(0,x);
    x=rson;
    while( lson )
        x=lson;
    return x;
}

int pre(int x){
    splay(0,x);
    x=lson;
    while( rson )
        x=rson;
    return x;
}

void Top(int x){
    int last=las(x);
    splay(0,pos[head]);   // splay只负责向上转，转到rt为止，一定要保证rt在x上面
    splay(pos[head],x);
    splay(x,last);
    t[last].son[0]=lson;
    t[lson].fa=last;
    lson=0;
    pushup(last);
    pushup(x);
}

void Bottom(int x){
    int pree=pre(x);
    splay(0,pos[tail]);
    splay(pos[tail],x);
    splay(x,pree);
    t[pree].son[1]=rson;
    t[rson].fa=pree;
    rson=0;
    pushup(pree);
    pushup(x);
}

int fin_order(int sz){
    int x=root;
    while( x ){
        if( sz<=t[lson].siz )
            x=lson;
        else if( sz==t[lson].siz+1 )
            return x;
        else{
            sz-=(t[lson].siz+1);
            x=rson;
        }
    }
}

int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&m);
    val[0]=head,val[n+1]=tail;
    for( int i=1 ; i<=n ; i++ )
        scanf("%d",&val[i]);
    root=build(0,n+1,0);
    char S[20];
    int s,tt;
    while( m-- ){
        scanf("%s",S);
        if( S[0]=='T' ){
            scanf("%d",&s);
            Top(pos[s]);
        }
        else if( S[0]=='B' ){
            scanf("%d",&s);
            Bottom(pos[s]);
        }
        else if( S[0]=='I' ){
            scanf("%d %d",&s,&tt);
            if( tt!=0 ){
                if( tt==1 ){
                    int lass=las(pos[s]),x=pos[s];
                    splay(0,pos[s]);
                    splay(pos[s],lass);
                    t[lass].son[0]=lson,t[lson].fa=lass;
                    lson=0;
                    rson=t[lass].son[1],t[t[lass].son[1]].fa=x;
                    t[lass].son[1]=x,t[x].fa=lass;
                    t[lass].fa=0,root=lass;
                    pushup(x);
                    pushup(lass);
                }
                else{
                    int pree=pre(pos[s]),x=pos[s];
                    splay(0,pos[s]);
                    splay(pos[s],pree);
                    t[pree].son[1]=rson,t[rson].fa=pree;
                    rson=0;
                    lson=t[pree].son[0],t[t[pree].son[0]].fa=x;
                    t[pree].son[0]=x,t[x].fa=pree;
                    t[pree].fa=0,root=pree;
                    pushup(x);
                    pushup(pree);
                }
            }
        }
        else if( S[0]=='A' ){
            scanf("%d",&s);
            splay(0,pos[s]);
            printf("%d\n",t[t[root].son[0]].siz-1);
        }
        else{
            scanf("%d",&s);
            printf("%d\n",t[fin_order(s+1)].val);
        }
    }
    return 0;
}

C++ 解法, 执行用时: 113ms, 内存消耗: 3320K, 提交时间: 2022-03-19 14:30:20 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N=2e5+10;
int read()
{
    int x=0,f=0,c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x; 
}

int sz[N],lch[N],rch[N],rnd[N],val[N],pos[N],fa[N];
int root,rx,ry,rz,cnt;
int n,m;

void SWAP(int x,int y)
{
	swap(val[x],val[y]); 
	pos[val[x]]=x; pos[val[y]]=y;
}

int _new(int x){sz[++cnt]=1; rnd[cnt]=rand(); val[cnt]=x; pos[x]=cnt; return cnt;}

void upd(int x){ sz[x]=sz[lch[x]]+sz[rch[x]]+1;}
//记录父亲的做法 
void split(int now,int k,int &x,int &y,int fax,int fay)
{
	if(!now){ x=y=0; return;}
	if(k>=sz[lch[now]]+1){ x=now;  fa[x]=fax; split(rch[now],k-sz[lch[now]]-1,rch[x],y,x,fay);}
	else {y=now; fa[y]=fay;  split(lch[now],k,x,lch[y],fax,y);}
	upd(now);
}

int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rnd[x]<rnd[y]){ rch[x]=merge(rch[x],y);  fa[rch[x]]=x; upd(x); return x;}
	else { lch[y]=merge(x,lch[y]);  fa[lch[y]]=y; upd(y); return y;}
}

//需要获取编号为x的书本的位置
//但是平衡树中不记录下标  
//但是我们只需要在logn的时间里获得位置即可 因此暴力向上跳就可以 
int findp(int x,int rt)
{
	int p=pos[x],ret=0;
	ret+=sz[lch[p]]+1;
	while(p!=rt)
	{
		if( rch[fa[p]]==p ) ret+=sz[lch[fa[p]]]+1;
		p=fa[p];
	}
	return ret;
}
//调试的时候不要拿完全二叉树来调试 
//向着左上方向走的才会被记入答案中 
int findk(int k,int rt)
{
	int now=rt;
	while(1)
	{
		int lsz=sz[lch[now]],rsz=sz[rch[now]];
		if(k==lsz+1) return now;
		else if(k<lsz+1) now=lch[now];
		else now=rch[now],k=k-lsz-1;
	}
}

void print(int x)
{
	if(!x) return;
	cout<<x<<" "<<lch[x]<<" "<<rch[x]<<endl;
	print(lch[x]);
//	cout<<val[x]<<" ";
	print(rch[x]);
}

void Top(int x)
{
//	print(root); puts("");	
	
	int p=findp(x,root);
	split(root,p,rx,rz,0,0);
	split(rx,p-1,rx,ry,0,0);//连续分裂的根的问题 
	root=merge( merge(_new(x),rx),rz );
//	print(root); puts("");
//	cout<<sz[root]<<endl;
}

void Bottom(int x)
{
//	print(root); puts("");
	int p=findp(x,root);
	split(root,p,rx,rz,0,0);
	split(rx,p-1,rx,ry,0,0);
	root=merge( merge(rx,rz),_new(x) );
//	print(root);puts("");
}

void Insert(int x,int t)
{
	if(t==0) return;
	int p=findp(x,root);
	int q=findk(p+t,root);
	SWAP(pos[x],q);
//	print(root);
}



int main()
{
//	freopen("data.txt","r",stdin);
	srand(1);
	n=read(); m=read();
	for(int i=1;i<=n;i++) 
	{
		int x=read();
		root=merge(root,_new(x));
	}
	
//	print(root); puts("");
	
	
	for(int i=1;i<=m;i++)
	{
		char s[10]; scanf("%s",s);
		char c=s[0]; int x=read();
		if(c=='T') Top(x);
		else if(c=='B') Bottom(x);
		else if(c=='I') Insert(x,read());
		else if(c=='A') printf("%d\n",findp(x,root)-1);
		else printf("%d\n",val[findk(x,root)]);		
//		print(root); puts("");
	}
}

上一题

© 2024 nowcoder.com