题解 P2596 【[ZJOI2006]书架】

题目的操作有5个，第一眼印象就是把暴力修改了一下，然后就过了，虽然时间复杂度好像比较高，不过最慢的点也只有312ms咯，能过就行是吧，重点是简单。 把其中的insert改了一下，insert(x,k)表示把x插入树中，并且使其在树中的中序遍历名次为k。 有了这个玩意写起来就方便多了 接下来开始暴力的各种操作 中序遍历的名次表示从上往下书柜的编号，每本书的编号就为它自己。 对于Top操作，把x删掉后插入并使其排名为1，就是把这本书拿出来再放到最上面去 对于Bottom操作，把x删掉后插入并使其排名为n，就是把这本书拿出来再放到最下面去 对于Insert操作，把x删掉后插入到排名+t上去 对于Ask操作，把x旋到最上面输出左边儿子个数，即它上面的书 对于Query操作，就是常规操作了 说一下这个insert吧，就是先把k-1名旋到最上面来，然后把x插进来 之后就完了 代码： ```cpp /******************************* Author:Morning_Glory LANG:C++ Created Time:2019年03月22日 星期五 15时46分12秒 *******************************/ #include <iostream> #include <fstream> #define rc(x) child[x][1] #define lc(x) child[x][0] using namespace std; const int maxn = 100005; int n,m,cnt,root,x,inc,rak; int size[maxn],fa[maxn]; int child[maxn][2]; char s[10]; //{{{splay inline void rotate (int x) { int f=fa[x],g=fa[f],c=rc(f)==x; fa[child[x][!c]]=f,child[f][c]=child[x][!c]; fa[f]=x,child[x][!c]=f; fa[x]=g; if (g) child[g][rc(g)==f]=x; size[f]=size[lc(f)]+size[rc(f)]+1; size[x]=size[lc(x)]+size[rc(x)]+1; } void splay (int x,int goal=0) { for (int f;(f=fa[x])!=goal;rotate(x)) if (fa[f]!=goal) rotate((x==rc(f))==(f==rc(fa[f]))?f:x); if (!goal) root=x; } //}}} //{{{kth int kth (int res)//找到排名为x的数 { int now=root; while (true){ if (lc(now)&&res<=size[lc(now)]) now=lc(now); else{ res-=size[lc(now)]+1; if (res<=0) return now; now=rc(now); } } } //}}} //{{{insert void insert (int x,int k)//将x插入且使其排名为k,并把它转上来 { if (k==1){ fa[x]=0, rc(x)=root,fa[root]=x, size[x]=size[root]+1, root=x; return;} int f=kth(k-1); splay(f); ++size[f]; rc(x)=rc(f); fa[x]=f; size[x]=size[rc(x)]+1; fa[rc(x)]=x; rc(f)=x; splay(x); } //}}} //{{{pre int pre (bool t)//t==0 前驱 t==1 后继 { int x=child[root][t]; t=!t; while (child[x][t]) x=child[x][t]; return x; } //}}} //{{{delet void delet (int x)//删除x { splay(x); int l=pre(0),r=pre(1); if (!l&&!r) size[x]=root=0; else if (!l) root=rc(x),fa[root]=rc(x)=size[x]=0; else if (!r) root=lc(x),fa[root]=lc(x)=size[x]=0; else{ splay(l),splay(r,l); lc(r)=0,--size[r],--size[l]; fa[x]=size[x]=0; } } //}}} //{{{Top void Top (int x) { delet(x); insert(x,1); } //}}} //{{{Bottom void Bottom (int x) { delet(x); insert(x,n); } //}}} //{{{Ask void Ask (int x) { splay(x); cout<<size[lc(x)]<<endl; } //}}} int main() { freopen("p2596.in","r",stdin); freopen("p2596.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;++i){ cin>>x; insert(x,i); } for (int i=1;i<=m;++i){ cin>>(s+1)>>x; if (s[1]=='I'){ cin>>inc; splay(x); rak=size[lc(x)]+1; delet(x); insert(x,rak+inc); } else if (s[1]=='A') Ask(x); else if (s[1]=='Q') cout<<kth(x)<<endl; else if (s[1]=='T') Top(x); else if (s[1]=='B') Bottom(x); } return 0; } ```