splay 练手用；
杭电的oj要手动开栈；
#include#pragma comment(linker, "/STACK:102400000,102400000")#include #include #define inf 999999#define maxn 1500009#define lch(rt) son[rt][0]#define rch(rt) son[rt][1]using namespace std;int son[maxn][2],fa[maxn];int val[maxn],size[maxn],flg[maxn];int cnt,root;int num[maxn];int n,m;void push_up(int rt){ size[rt]=size[lch(rt)]+size[rch(rt)]+1;}void push_down(int rt){ if(flg[rt]) { swap(lch(rt),rch(rt)); if(lch(rt)) flg[lch(rt)]^=1; if(rch(rt)) flg[rch(rt)]^=1; flg[rt]=0; }}void newnode(int &rt,int f,int v){ rt=++cnt; lch(rt)=rch(rt)=0; val[rt]=v; fa[rt]=f; size[rt]=1; flg[rt]=0;}void build(int l,int r,int &rt,int f){ if(l>r)return; int mid=(l+r)>>1; newnode(rt,f,num[mid]); build(l,mid-1,lch(rt),rt); build(mid+1,r,rch(rt),rt); push_up(rt);}void ini(){ cnt=root=0; lch(0)=rch(0)=0; fa[0]=val[0]=flg[0]=size[0]=0; newnode(root,0,0); newnode(rch(root),root,inf); build(1,n,lch(rch(root)),rch(root)); push_up(rch(root)); push_up(root);}void rotate(int x,int kind)//0->left,1->right{ push_down(x); int y=fa[x]; son[y][kind^1]=son[x][kind]; fa[son[x][kind]]=y; if(fa[y]) son[fa[y]][son[fa[y]][1]==y]=x; fa[x]=fa[y]; son[x][kind]=y; fa[y]=x; push_up(y);}void splay(int rt,int goal)//将rt节点旋转到goal的右子节点{ if(rt!=goal) { push_down(rt); while(fa[rt]!=goal) { if(lch(fa[rt])==rt) rotate(rt,1); else rotate(rt,0); } push_up(rt); if(!goal)root=rt; }}int select(int k){ int rt=root; push_down(rt); while(size[lch(rt)]+1!=k) { if(size[lch(rt)]+1>=k) rt=lch(rt); else { k-=(size[lch(rt)]+1); rt=rch(rt); } push_down(rt);//不加就超时； } return rt;}int cntt;void dfs(int rt){ push_down(rt); if(lch(rt)) dfs(lch(rt)); num[cntt++]=val[rt]; if(rch(rt)) dfs(rch(rt));}void flip(int a,int b){ a=select(a-1); splay(a,0); b=select(b+1); splay(b,a); flg[lch(b)]^=1;}char s[20],t[5];int main(){ int tt; int ld,rd; scanf("%d",&tt); while(tt--) { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&num[i]); ini(); scanf("%d%d",&ld,&rd); ld++; rd++; int cot=0; int a,b; scanf("%d",&m); int dat; while(m--) { scanf("%s",s); if(s[0]=='M') { scanf("%s",t); if(t[0]=='R'&&s[4]=='R') rd++; else if(t[0]=='R'&&s[4]=='L') rd--; else if(t[0]=='L'&&s[4]=='R') ld++; else ld--; } else if(s[0]=='I') { cot++; scanf("%s%d",t,&dat); if(t[0]=='L') { a=select(ld-1); b=select(ld); } else { a=select(rd); b=select(rd+1); } rd++; splay(a,0); splay(b,a); newnode(lch(b),b,dat); fa[lch(b)]=b; push_up(b); push_up(a); } else if(s[0]=='R') { flip(ld,rd); } else if(s[0]=='D') { cot--; scanf("%s",t); if(t[0]=='L') { a=select(ld-1); b=select(ld+1); } else { a=select(rd-1); b=select(rd+1); } rd--; splay(a,0); splay(b,a); push_down(a); push_down(b); lch(b)=0; push_up(b); push_up(a); } } a=select(2); b=select(n+cot+1); splay(a,0); splay(b,a); n+=cot; cntt=0; dfs(root); for(int i=1;i