正題

題目鏈接:https://www.luogu.com.cn/problem/P3850

---

題目大意

一個書架上有$n$本書，進行$m$次插入操作，然后$q$次詢問一個位置上的書。

---

解題思路

用$Splay$進行插入操作，然后直接查詢即可

---

$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]]);} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P3850-[TJOI2007]书架【Splay】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。