关键词：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=8e4+5;
4 const int inf=1e9;
5 int fa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;
6 void update(int x)
7 {
8 size[x]=size[c[x][0]]+size[c[x][1]]+1;
9 }
10 void rotate(int x,int &k)
11 {
12 int y=fa[x],z=fa[y];
13 int l=(c[y][1]==x);int r=l^1;
14 if(y==k)k=x;else c[z][c[z][1]==y]=x;
15 fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
16 c[y][l]=c[x][r];c[x][r]=y;
17 update(y);update(x);
18 }
19 void splay(int x,int &k)
20 {
21 while(x!=k)
22 {
23 int y=fa[x],z=fa[y];
24 if(y!=k)
25 {
26 if(x==c[y][0]^y==c[z][0])rotate(x,k);
27 else rotate(y,k);
28 }
29 rotate(x,k);
30 }
31 }
32 int find(int x,int k)
33 {
34 if(size[c[x][0]]+1==k)return x;
35 else if(size[c[x][0]]>=k)return find(c[x][0],k);
36 else return find(c[x][1],k-size[c[x][0]]-1);
37 }
38 void del(int k)
39 {
40 int x=find(rt,k-1);int y=find(rt,k+1);
41 splay(x,rt);splay(y,c[x][1]);
42 int z=c[y][0];c[y][0]=0;fa[z]=size[z]=0;
43 update(y);update(x);
44 }
45 void remove(int q,int w)
46 {
47 int k=pos[q],rank,x,y;
48
49 splay(k,rt);rank=size[c[rt][0]]+1;
50 del(rank);
51 if(w==inf)x=find(rt,n),y=find(rt,n+1);
52 else if(w==-inf)x=find(rt,1),y=find(rt,2);
53 else x=find(rt,rank+w-1),y=find(rt,rank+w);
54 splay(x,rt);splay(y,c[x][1]);
55 size[k]=1;fa[k]=y;c[y][0]=k;
56 update(y);update(x);
57 }
58 void build(int l,int r,int f)
59 {
60 if(l>r)return;
61 int mid=l+r>>1;
62 fa[mid]=f;c[f][mid>=f]=mid;v[mid]=a[mid];
63 if(l==r)
64 {
65 size[l]=1;return;
66 }
67 build(l,mid-1,mid);build(mid+1,r,mid);
68 update(mid);
69 return;
70 }
71 int main()
72 {
73 scanf("%d%d",&n,&m);
74 for(int i=2;i<=n+1;++i)
75 {
76 scanf("%d",&a[i]);pos[a[i]]=i;
77 }
78 build(1,n+2,0);rt=(n+3)>>1;char s[10];int k,ss,t;
79 for(int i=1;i<=m;++i)
80 {
81 scanf("%s",s);
82 if(s[0]==‘Q‘)
83 {
84 scanf("%d",&k);
85 printf("%d
",v[find(rt,k+1)]);
86 }
87 else if(s[0]==‘T‘)
88 {
89 scanf("%d",&k);
90 remove(k,-inf);
91 }
92 else if(s[0]==‘B‘)
93 {
94 scanf("%d",&k);
95 remove(k,inf);
96 }
97 else if(s[0]==‘I‘)
98 {
99 scanf("%d%d",&ss,&t);remove(ss,t);
100 }
101 else
102 {
103 scanf("%d",&k);k=pos[k];
104 splay(k,rt);
105 printf("%d
",size[c[rt][0]]-1);
106 }
107 }
108 return 0;
109 }
[bzoj1861][zjoi2006]book书架
[BZOJ1861][Zjoi2006]Book书架试题描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一... 查看详情
bzoj1861[zjoi2006]book书架
1#include<bits/stdc++.h>2usingnamespacestd;3constintN=8e4+5;4constintinf=1e9;5intfa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;6voidupdate(intx)7{8size[x]=size[c[x][0]]+size[c[x][1]]+1;9}10voidr 查看详情
bzoj1861:[zjoi2006]book书架
这题想写三次了。结果前两次太困╯﹏╰没写成，大数据结构题就是烦人啊。没什么值得注意的，就按题意一步步来吧。（写了map表示对应树上位置，担心编号大爆掉，不加好像也没啥关系）#include<cstdio>#include<iostream>#i... 查看详情
bzoj1861[zjoi2006]book书架——splay
【题目分析】 模板题目。 首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情
bzoj1861:[zjoi2006]book书架splay
1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[题解]bzoj1861book书架-splay
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
bzoj1861：[zjoi2006]书架——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1861（题面复制于洛谷）题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一... 查看详情
[bzoj1861][zjoi2006]书架
BZOJLuoguDescription小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太... 查看详情
[zjoi2006]book书架
pre.cjk{font-family:"DroidSansFallback",monospace}p{margin-bottom:0.25cm;line-height:120%}a:link{}1861:[Zjoi2006]Book书架TimeLimit:4Sec MemoryLimit:64MBSubmit:1581 Solved:884[Submi 查看详情
bzoj1861:[zjoi2006]book书架（平衡树）(代码片段)
原题链接题目描述：小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些... 查看详情
1861.[zjoi2006]书架平衡树-splay(代码片段)
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[zjoi2006]书架(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树 时间复杂度：O(MlogN)[代码] &n 查看详情
[zjoi2006]book书架(代码片段)
DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
「luogu2596」[zjoi2006]书架(代码片段)
用平衡树维护每本书的位置1#include<bits/stdc++.h>2usingnamespacestd;3constintN=80010;4intn,m,maxpos,minpos,book[N<<2],bookpos[N];5introot,fa[N<<2],ch[N<<2][2],siz[N<<2],pos[N<<2 查看详情
bzoj1861书架splay版
单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情
bzoj1861书架(代码片段)
题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。操作3，其... 查看详情