题解 P2596 【[ZJOI2006]书架】
critnos
·
·
题解
发篇题解庆祝一下。
需要的数据结构：
一个数组：a；一个map：b；一个平衡树（pb_ds实现）：t。
$b$：$key$为书的编号在书架中的位置，映射的值是书的编号。
$t$：模拟书架，存储的是所有书的虚拟位置。
还要两个变量：$l$，$r$。$l$存储书架的顶端编号，$r$存储书架的底端编号。
**操作1：把编号为S的书放在最上面**
每个数据结构都要修改。对于$t$和$b$，删除$key=a_S$的节点，添加$key=l$，$b_l$仍然映射$S$。对于$a$，直接修改$a_S$为$l$。同时还要把$l-1$。注意修改顺序。
操作2同上。
**操作3：若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书**
每个数据结构都要修改。对于$b$，交换$b_{a_S}$和$b_u$，$u$为在$t$中$a_S$的前驱或后继（见【【模板】普通平衡树】）。对于$a$，直接修改$a_S$为$l$。$t$不用修改，因为排名并没有发生改变。
**操作4：询问编号为S的书的上面目前有多少本书**
求$t$中$a_S$的排名。
**操作5：询问从上面数起的第S本书的编号**
输出$b_v$,$v$为$t$中排名为$s$的数。
所有的操作的时间复杂度均为$O(\log n)$。
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> t;
int a[80005];
map<int,int> b;
/*
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本书的编号。
*/
int main()
{
int x,y,n,m,i,w,l,r,u;
char opt[10];
scanf("%d%d",&n,&m);
l=0,r=n+1;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
a[x]=i;
b[i]=x;
t.insert(i);
}
while(m--)
{
scanf("%s%d",&opt,&x);
w=a[x];
if(opt[0]=='T')
{
t.erase(t.lower_bound(w));
t.insert(l);
a[x]=l;
b.erase(w);
b[l]=x;
l--;
}
if(opt[0]=='B')
{
t.erase(t.lower_bound(w));
t.insert(r);
a[x]=r;
b.erase(w);
b[r]=x;
r++;
}
if(opt[0]=='I')
{
scanf("%d",&y);
if(y==-1)
{
u=*(--t.lower_bound(w));
swap(a[x],a[b[u]]);
swap(b[w],b[u]);
}
if(y==1)
{
u=*(t.lower_bound(w+1));
swap(a[x],a[b[u]]);
swap(b[w],b[u]);
}
}
if(opt[0]=='A')
printf("%d\n",t.order_of_key(w));
if(opt[0]=='Q')
printf("%d\n",b[(*t.find_by_order(x-1))]);
}
}
```
完。