rt，从 P4008 过来的

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,pos,root,cnt,L,R,p;
struct FHQ_Treap
{
	int ls,rs;
	char val;
	int pri,siz,tag;
}t[N];
int newNode(char x)
{
	t[++cnt]={0,0,x,rand(),1,0};
	return cnt;
}
void update(int u)
{
	t[u].siz=t[t[u].ls].siz+t[t[u].rs].siz+1;
}
void push_down(int u)
{
	if(!t[u].tag) return;
	swap(t[u].ls,t[u].rs);
	t[t[u].ls].tag^=1;
	t[t[u].rs].tag^=1;
	t[u].tag=0;
}
void spilt(int u,int x,int &L,int &R)
{
	if(!u)
	{
		L=R=0;
		return;
	}
	push_down(u);
	if(t[t[u].ls].siz+1<=x)
	{
		L=u;
		spilt(t[u].rs,x-t[t[u].ls].siz-1,t[u].rs,R);
	}
	else
	{
		R=u;
		spilt(t[u].ls,x,L,t[u].ls);
	}
	update(u);
}
int merge(int L,int R)
{
	if(!L||!R) return L|R;
	if(t[L].pri>t[R].pri)
	{
		push_down(L);
		t[L].rs=merge(t[L].rs,R);
		update(L);
		return L;
	}
	else
	{
		push_down(R);
		t[R].ls=merge(L,t[R].ls);
		update(R);
		return R;
	}
}
int main()
{
	srand(time(0));
	scanf("%d",&n);
	while(n--)
	{
		int len;
		char opt[15];
		scanf("%s",&opt);
		char ch=getchar();
		if(opt[0]=='M') scanf("%d",&pos);
		if(opt[0]=='I')
		{
			scanf("%d",&len);
			spilt(root,pos,L,R);
			for(int i=1;i<=len;i++)
			{
				char ch=getchar();
				while(ch<32||ch>126) ch=getchar();
				L=merge(L,newNode(ch));
			}
			root=merge(L,R);
		}
		if(opt[0]=='D')
		{
			scanf("%d",&len);
			spilt(root,pos+len,L,R);
			spilt(L,pos,L,p);
			root=merge(L,R);
		}
		if(opt[0]=='R')
		{
			scanf("%d",&len);
			spilt(root,pos+len,L,R);
			spilt(L,pos,L,p);
			t[p].tag^=1;
			root=merge(merge(L,p),R);
		}
		if(opt[0]=='G')
		{
			spilt(root,pos+1,L,R);
			spilt(L,pos,L,p);
			printf("%c",t[p].val);
			if(t[p].val!='\n') printf("\n");
			root=merge(merge(L,p),R);
		}
		if(opt[0]=='P') pos--;
		if(opt[0]=='N') pos++;
	}
	return 0;
}