正题
题目链接:https://www.luogu.com.cn/problem/P3850
题目大意
一个书架上有
n
n
n本书，进行
m
m
m次插入操作，然后
q
q
q次询问一个位置上的书。
解题思路
用
S
p
l
a
y
Splay
Splay进行插入操作，然后直接查询即可
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=2e5;
int n
,m
,root
;char s
[N
][15];
int tot
,t
[N
][2],siz
[N
],fa
[N
];
void PushUp(int x
)
{siz
[x
]=siz
[t
[x
][0]]+siz
[t
[x
][1]]+1;return;}
bool Direct(int x
)
{return t
[fa
[x
]][1]==x
;}
void Connect(int x
,int y
,int son
)
{t
[x
][son
]=y
;fa
[y
]=x
;return;}
void Rotate(int x
){
int y
=fa
[x
],z
=fa
[fa
[x
]];
int xs
=Direct(x
),ys
=Direct(y
);
int k
=t
[x
][xs
^1];
Connect(y
,k
,xs
);
Connect(x
,y
,xs
^1);
Connect(z
,x
,ys
);
PushUp(y
);PushUp(x
);
return;
}
void Splay(int x
,int f
){
while(fa
[x
]!=f
){
int up
=fa
[x
];
if(fa
[up
]==f
)Rotate(x
);
else if(Direct(x
)==Direct(up
))
Rotate(up
),Rotate(x
);
else Rotate(x
),Rotate(x
);
}
return;
}
int Find(int x
,int k
){
if(siz
[t
[x
][0]]>=k
)return Find(t
[x
][0],k
);
if(siz
[t
[x
][0]]+1==k
)return x
;
return Find(t
[x
][1],k
-siz
[t
[x
][0]]-1);
}
int main()
{
scanf("%d",&n
);
siz
[1]=1;
for(int i
=1;i
<=n
;i
++){
scanf("%s",s
[i
+1]);
fa
[i
]=i
+1;t
[i
+1][0]=i
;
PushUp(i
+1);
}
fa
[n
+1]=n
+2;t
[n
+2][0]=n
+1;
PushUp(n
+2);root
=tot
=n
+2;
scanf("%d",&m
);
while(m
--){
scanf("%s",s
[++tot
]);
int l
;scanf("%d",&l
);l
++;
int x
=Find(root
,l
),y
=Find(root
,l
+1);
Splay(x
,0);Splay(y
,x
);
t
[y
][0]=tot
;fa
[tot
]=y
;siz
[tot
]=1;
Splay(tot
,0);root
=tot
;
}
scanf("%d",&m
);
while(m
--){
int l
;scanf("%d",&l
);l
++;
int x
=Find(root
,l
),y
=Find(root
,l
+2);
Splay(x
,0);Splay(y
,x
);root
=x
;
printf("%s\n",s
[t
[y
][0]]);
}
}
