40pts，2~5 AC，其余 WA

#include <ctime>
#include <cstdio>
#include <random>
#include <cstring>

const int N=5e6+10;

std::mt19937 rnd(time(0));

struct fhq_Treap {
	#define ls(p) (tr[p].ls)
	#define rs(p) (tr[p].rs)
	
	struct node {
		char val;int key,siz;
		int ls,rs;
	}tr[N];int idx,rt;
	
	void push_up(int p) {tr[p].siz=tr[ls(p)].siz+tr[rs(p)].siz+1;}
	
	int New(char c) {
		tr[++idx].val=c;tr[idx].siz=1;
		ls(idx)=rs(idx)=0;tr[idx].key=rnd();
		return idx;
	}
	
	void split(int p,int k,int &x,int &y) {
		if(!p) {x=y=0;return;}int siz=tr[ls(p)].siz;
		if(k<=siz) {y=p;split(ls(p),k,x,ls(p));} 
		else {x=p;split(rs(p),k-siz-1,rs(p),y);}
		push_up(p);
	}
	
	int merge(int x,int y) {
		if(!x||!y) return x^y;
		if(tr[x].key>=tr[y].key) {
			rs(x)=merge(rs(x),y);
			push_up(x);return x;
		} else {
			ls(y)=merge(x,ls(y));
			push_up(y);return y;
		}
	}
	
	int sta[N],top;
	
	void print(int p) {
		if(ls(p)) print(ls(p));
		printf("%c",tr[p].val);
		if(rs(p)) print(rs(p));
	}
	
	int build(char c[],int len) {
		top=0;int root=0;
		for(int i=0;i<len;i++) {
			int p=New(c[i]);
			while(top&&tr[p].key>tr[sta[top]].key) {push_up(sta[top]);--top;}
			if(top) {tr[p].ls=tr[sta[top]].rs;tr[sta[top]].rs=p;} 
			else {tr[p].ls=root;root=p;}
			sta[++top]=p;
		}
		while(top) {push_up(sta[top]);--top;}
		return root;
	}
	
	void insert(char c[],int k,int n) {
		int p=build(c,n);int x=0,y=0;
		split(rt,k,x,y);rt=merge(merge(x,p),y);
	}
	
	void del(int l,int r) {
		int x=0,y=0;split(rt,r+1,x,y);
		int p=0;split(x,l,x,p);
		rt=merge(x,y);
	}
	
	void query(int l,int r) {
		int x=0,y=0;split(rt,r,x,y);
		int p=0;split(x,l,x,p);
		print(p);puts("");
		rt=merge(merge(x,p),y);
	}
	
	#undef ls
	#undef rs
}T;

char op[10],c[N];

int main() {
	int m=0,p=0;scanf("%d",&m);
	while(m--) {
		scanf(" %s",op);
		if(op[0]=='M') {
			scanf("%d",&p);
		} else if(op[0]=='I') {
			int n;scanf("%d",&n);
			int idx=0;char x=getchar();
			while(idx<n) {
				if(x<32||x>126);
				else c[idx++]=x;
				x=getchar();
			}
			T.insert(c,p,n);
		} else if(op[0]=='D') {
			int n;scanf("%d",&n);
			T.del(p,p+n);
		} else if(op[0]=='G') {
			int n;scanf("%d",&n);
			T.query(p,p+n);
		} else if(op[0]=='P') --p;
		else if(op[0]=='N') ++p;
	}
	return 0;
}