splay瞎搞一下，正解是分块数组或分块链表，但是学不会啊！
#include<cstdio> #include<cstdlib> #include<iostream> #include<string> #include<set> #include<algorithm> #include<vector> #include<queue> #include<list> #include<cmath> #include<cstring> #include<map> #include<stack> using namespace std; #define INF 0x3f3f3f3f #define maxn 2005 #define ull unsigned long long #define ll long long #define hashmod 99999839 #define mod 9997 int son[maxn][2],fa[maxn],sz[maxn],root,len,q; char s[maxn],v[maxn],ch; //kpmsrzxxzu inline void update(int o){ sz[o] = 1; if(son[o][0] != -1) sz[o] += sz[son[o][0]]; if(son[o][1] != -1) sz[o] += sz[son[o][1]]; } inline int isrson(int p,int f){ if(f == -1) return 0; return son[f][1] == p; } inline void changeson(int p,int f,int v){ if(f != -1) son[f][v] = p; if(p != -1) fa[p] = f; if(f == -1) root = p; } int build(int l,int r){ if(l > r) return -1; int o = len; len++; if(l == r){son[o][0] = son[o][1] = -1,sz[o] = 1,v[o] = s[l];return o;} int mid = (l + r) >> 1,ls,rs; v[o] = s[mid],ls = build(l,mid-1),rs = build(mid+1,r); changeson(ls,o,0),changeson(rs,o,1),update(o); return o; } void rotate(int p){//只会出现祖辈不存在的情况 int f = fa[p],g = fa[f]; int u = isrson(p,f),v = isrson(f,g); changeson(son[p][u^1],f,u),changeson(f,p,u^1),changeson(p,g,v); update(f); } void splay(int p,int tar){ if(fa[p] == tar) return; while(fa[p] != tar && fa[fa[p]] != tar){ int f = fa[p],g = fa[f];//保证了父亲及其祖先存在 int u = isrson(p,f),v = isrson(f,g); if(u ^ v) rotate(p),rotate(p); else rotate(f),rotate(p); } if(fa[p] != tar) rotate(p); update(p); } int findtr(){ int p = root,ls = son[p][0],rs = son[p][1]; if(q >= sz[p]) q = sz[p] - 1; while(1){ if(ls == -1){ if(q == 1) break; else p = rs,q--; ls = son[p][0],rs = son[p][1]; continue; } if(sz[ls] >= q) p = ls; else if(sz[ls] + 1 == q) break; else p = rs,q = q - sz[ls] - 1; ls = son[p][0],rs = son[p][1]; } return p; } void insert(){ int p = findtr(); splay(p,-1); int o = len; len++,v[o] = ch; changeson(root,o,0),changeson(son[root][1],o,1); son[root][1] = -1,fa[o] = -1; update(root); root = o; update(root); } void query(){ int p = findtr(); printf("%c ",v[p]); splay(p,-1); } signed main(){ // freopen("a.in","r",stdin); // freopen("b.out","w",stdout); // int k = 0; while(~scanf("%s",s + 1)){ int t = strlen(s + 1); len = 0; s[0] = ' ',s[t + 1] = ' '; root = build(0,t + 1); fa[root] = -1; int n; char op[5]; scanf("%d",&n); // printf("Case %d: ",++k); for(register int i = 1;i <= n;++i){ scanf("%s",op); if(op[0] == 'Q') scanf("%d",&q),q++,query(); else scanf("%s%d",op,&q),ch = op[0],insert(); } } return 0; }