P2596 [ZJOI2006]书架 题解
cmach_socket · · 个人记录
这是一种普通线段树的做法
可以发现我们要维护每个点的位置以及编号，如果暴力处理每次操作的编号必定会TLE，但是可以发现这道题每次操作只涉及一个或者两个点，于是把可以想象这是一个长度为3*n的书架：
-
记录这些信息：
书堆顶端位置，书堆末端位置，每个架子上有没有书，编号是多少，每本书放在那个位置
于是可以用线段树维护每个架子上有没有书，编号是多少，用id数组维护每本书放在那个位置，用ls和rs变量维护书堆顶端位置，书堆末端位置
-
Top：将编号为s的书拿到书堆顶端位置的上一个位置，并更新信息，
等价于在线段树上修改id[s]的位置并将s移动到 ls-1;
-
Bottom:将编号为s的书拿到书堆底端位置的下一个位置，并更新信息
等价于在线段树上修改id[s]的位置并将s移动到 rs+1;
-
Insert:交换相邻两本书（t=-1为前一本，t=1为后一本）
等价于在线段树上查询s的前驱/后继并与s交换
-
Ask:求编号为s的书是第几本
等价于区间查询ls-id[s]的非空书架数量-1
-
Query：可以在线段树上二分完成
-
时间复杂度只有 比平衡树小了不少，实测5*n最慢也只有88ms（不开O2）
代码也短了一些（没压行）：
#include<stdio.h>
#include<algorithm>
#define lk k<<1
#define rk k<<1|1
#define MAXN 400005//理论3*n就可以了，但是我死活过不了RE#8,怒开5*n
using namespace std;
int ls,rs;
class node{
public:
int l,r,w,siz;
//w:这个位置上书的编号，siz:有多少书
}t[MAXN<<2];
int n,m,id[MAXN],a[MAXN],tx,ty,tmp,an,t2;
// id:每个节点的位置
char op[10];
void update(int k){
t[k].siz=t[lk].siz+t[rk].siz;//统计区间有多少非空书架
}
void build(int k,int l,int r){
t[k].l=l,t[k].r=r;
if(l==r){
t[k].siz=0;
if(l>2*n and l<=3*n){//最开始把书堆放在中间，保证top和bottom操作有充足的空间
t[k].w=a[l-2*n];
t[k].siz=1;
}
return ;
}
int mid=(l+r)>>1;
build(lk,l,mid);
build(rk,mid+1,r);
update(k);
}
void change(int k,int x,int y){
if(t[k].l==t[k].r){
t[k].w=y;
if(!t[k].w)t[k].siz=0;//编号为0,即没有书
else t[k].siz=1;
return ;
}
int mid=(t[k].l+t[k].r)>>1;
if(x<=mid)change(lk,x,y);
else change(rk,x,y);
update(k);
}
int qask(int k,int l,int r){//求[l,r]中有几本书
if(l<=t[k].l and r>=t[k].r){
return t[k].siz;
}
int mid=(t[k].l+t[k].r)>>1,ans=0;
if(l<=mid)ans+=qask(lk,l,r);
if(r>mid)ans+=qask(rk,l,r);
return ans;
}
int kth(int k,int s){//求从最上面起第s本书的编号。
if(t[k].l==t[k].r){
return t[k].w;
}
if(t[lk].siz<s){//要求本数的大于左子树的大小，说明在右子树
return kth(rk,s-t[lk].siz);//记得减掉左子树的大小
}
else{
return kth(lk,s);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
id[a[i]]=i+2*n;//实际上编号为a[i]的书放的位置
}
build(1,1,5*n);
ls=2*n+1,rs=3*n;
for(int i=1;i<=m;i++){
scanf("%s",op);
if(op[0]=='T'){
scanf("%d",&tx);
change(1,id[tx],0);//移开这个位置
id[tx]=--ls;
change(1,id[tx],tx);//移到顶端
}
else if(op[0]=='B'){
scanf("%d",&tx);
change(1,id[tx],0);//移开这个位置
id[tx]=++rs;
change(1,id[tx],tx);//移到底部
}
else if(op[0]=='I'){
scanf("%d%d",&tx,&ty);
tmp=qask(1,ls,id[tx]);//先求tx是第几本，这样才能通过kth找到前驱后继
an=kth(1,tmp+ty);//求前驱/后继
//交换
change(1,id[tx],an);
change(1,id[an],tx);
swap(id[tx],id[an]);
//交换
}
else if(op[0]=='A'){
scanf("%d",&tx);
printf("%d\n",qask(1,ls,id[tx])-1);
}
else{
scanf("%d",&tx);
printf("%d\n",kth(1,tx));
}
}
return (0^0);//完结撒花
}