室内设计师个人网站,国际热点新闻,wordpress找不到页面,wordpress可以做cms吗P2596 [ZJOI2006]书架 题目描述 小T有一个很大的书柜。这个书柜的构造有些独特#xff0c;即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候#xff0c;每次取出一本书#xff0c;看完后放回书柜然后再拿下一本。由于这些书太有吸引力…P2596 [ZJOI2006]书架 题目描述 小T有一个很大的书柜。这个书柜的构造有些独特即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候每次取出一本书看完后放回书柜然后再拿下一本。由于这些书太有吸引力了所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的所以每次放书的时候至少能够将那本书放在拿出来时的位置附近比如说她拿的时候这本书上面有X本书那么放回去时这本书上面就只可能有X-1、X或X1本书。 当然也有特殊情况比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面然后转身离开。 久而久之小T的书柜里的书的顺序就会越来越乱找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序处理她看书时的一些操作以及回答她的两个提问(1)编号为X的书在书柜的什么位置(2)从上到下第i本书的编号是多少。 输入输出格式 输入格式 第一行有两个数nm分别表示书的个数以及命令的条数第二行为n个正整数第i个数表示初始时从上至下第i个位置放置的书的编号第三行到m2行每行一条命令。命令有5种形式 1 Top S——表示把编号为S的书放在最上面。 2 Bottom S——表示把编号为S的书放在最下面。 3 Insert S T——T∈{-101}若编号为S的书上面有X本书则这条命令表示把这本书放回去后它的上面有XT本书 4 Ask S——询问编号为S的书的上面目前有多少本书。 5 Query S——询问从上面数起的第S本书的编号。 输出格式 对于每一条Ask或Query语句你应该输出一行一个数代表询问的答案。 说明 100%的数据n,m 80000 这是我做的第一道非板子的平衡树题目写调大概花了2个小时稍稍有点困先以时间压到1个小时为目标了。 很显然这颗平衡树是一颗区间树用来平衡的域是书的相对位置大小我们用树的大小信息来查询某个点在书架的相对位置而不去直接存储这个相对位置以比较这应该是区间树的一个重要特点。 用\(pos[i]\)维护编号为\(i\)的书对应哪个节点。 对于操作 放在最上面/下面就先删掉然后加点 添加的话只有两个情况就先把要添加的节点伸展到根然后和它的前驱/后继交换即可 两个询问互为逆操作有关排名的 #include cstdio
#include iostream
#define ls t[now].ch[0]
#define rs t[now].ch[1]
#define f t[now].par
#define s t[now].ch[typ]
using namespace std;
const int N160010;
struct Splay
{int ch[2],par,siz,num;
}t[N];
int root,tot0,n,m,x,a[N],pos[N];//编号为i的书对应的当前点的编号
string S;
int identity(int now)
{return t[f].ch[1]now;
}
void connect(int fa,int now,int typ)
{ffa;t[fa].ch[typ]now;
}
void updata(int now)
{t[now].sizt[ls].sizt[rs].siz1;
}
void rotate(int now)
{int pf,typidentity(now);connect(p,t[now].ch[typ^1],typ);connect(t[p].par,now,identity(p));connect(now,p,typ^1);updata(p),updata(now);
}
void splay(int now,int to)
{tot[to].par;for(int typ;f!to;rotate(now))if(t[f].par!to)rotate(identity(now)identity(f)?f:now);if(!to) rootnow;
}
int New(int dat)
{t[tot].numdat;t[tot].siz1;return tot;
}
void free(int now)
{t[now].num0;t[now].siz0;t[now].par0;ls0;rs0;if(totnow) tot--;
}
void find(int x)//当前排名为x的书的编号
{int nowroot;while(t[ls].siz1!x)nowt[now].ch[t[ls].siz1x?x-t[ls].siz1,1:0];splay(now,root);printf(%d\n,t[now].num);
}
int get_max(int now,int typ)
{if(typ) t[now].siz;return rs?get_max(rs,typ):now;
}
int get_min(int now,int typ)
{if(typ) t[now].siz;return ls?get_min(ls,typ):now;
}
void extrack(int now)//删除编号为now的点
{splay(now,root);if(!ls){rootrs;connect(0,root,1);free(now);return;}int rtget_max(ls,0);splay(rt,ls);connect(rt,rs,1);connect(0,rt,1);updata(rt);rootrt;free(now);
}
void rank(int now)
{splay(now,root);printf(%d\n,t[ls].siz);
}
void top(int now,int num)//节点编号和书的编号
{extrack(now);int faget_min(root,1);connect(fa,nowNew(num),0);pos[num]now;updata(now);
}
void bottom(int now,int num)
{extrack(now);int faget_max(root,1);connect(fa,nowNew(num),1);pos[num]now;updata(now);
}
void exchange(int to,int now)
{swap(pos[t[to].num],pos[t[now].num]);swap(t[to].num,t[now].num);
}
void insert(int now,int T)
{if(!T) return;splay(now,root);if(T1) exchange(get_min(rs,0),now);else exchange(get_max(ls,0),now);
}
int build(int l,int r,int fa)
{if(lr) return 0;int nowlr1;t[now].parfa;t[now].numa[now];updata(now);if(lr) return now;lsbuild(l,now-1,now);rsbuild(now1,r,now);updata(now);return now;
}
/*void write(int now)
{if(!now) return;write(ls);printf(%d ,t[now].num);write(rs);
}*/
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,ai);pos[a[i]]i;}connect(0,rootbuild(1,n,0),1);totn;for(int i1;im;i){cinS;scanf(%d,x);if(STop)top(pos[x],x);else if(SBottom)bottom(pos[x],x);else if(SInsert){int T;scanf(%d,T);insert(pos[x],T);}else if(SAsk)rank(pos[x]);elsefind(x);//write(root);//printf(%d\n);}return 0;
}2018.6.14 转载于:https://www.cnblogs.com/butterflydew/p/9182269.html
