题目P4008

code:

#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
long long n;
struct node{
	char val;
	long long ls,rs,cnt,fa;
}tr[9000001];
long long root=0;
void push(long long i) {
	tr[3000000].cnt=0;
	tr[i].cnt=tr[tr[i].ls].cnt+tr[tr[i].rs].cnt+(i!=0);
}
long long cnt=0;
void Rotate(long long i) {
	if(i==root) return;
	if(tr[i].ls<=cnt||tr[i].rs<=cnt) {
		if(tr[tr[i].ls].cnt>tr[tr[i].rs].cnt) {
			long long tp=tr[i].ls;
			tr[i].ls=tr[tp].rs;
			tr[tr[tp].rs].fa=i;
			tr[tp].rs=i;
			if(tr[tr[i].fa].ls==i) {
				tr[tp].fa=tr[i].fa;
				tr[tr[i].fa].ls=tp;
			} else {
				tr[tp].fa=tr[i].fa;
				tr[tr[i].fa].rs=tp;
			}
			tr[i].fa=tp;
			push(i);
			push(tp);
		} else {
			if(tr[tr[i].rs].cnt) {
				long long tp=tr[i].rs;
				tr[i].rs=tr[tp].ls;
				tr[tr[tp].ls].fa=i;
				tr[tp].ls=i;
				if(tr[tr[i].fa].ls==i) {
					tr[tp].fa=tr[i].fa;
					tr[tr[i].fa].ls=tp;
				} else {
					tr[tp].fa=tr[i].fa;
					tr[tr[i].fa].rs=tp;
				}
				tr[i].fa=tp;
				push(i);
				push(tp);
			}
		}
	}
}
void Insert(long long i,long long side,char val) {
	if(side==0&&tr[i].ls>cnt) {
		tr[i].ls=++cnt,tr[cnt]=(node){val,3000000,3000000,1,i};
		Rotate(i);
		return;
	}
	if(tr[tr[i].ls].cnt>=side&&tr[i].ls<=cnt) {
		Insert(tr[i].ls,side,val);
		Rotate(i);
		return;
	}
	if(tr[i].cnt-tr[tr[i].rs].cnt<=side) 
		if(tr[i].rs<=cnt)
			Insert(tr[i].rs,side-tr[i].cnt+tr[tr[i].rs].cnt,val);
		else
			tr[i].rs=++cnt,tr[cnt]=(node){val,3000000,3000000,1,i};
	tr[i].cnt++;
	Rotate(i);
}
long long over(long long i) {
	return (tr[i].rs<=cnt?over(tr[i].rs):i);
}
void let(long long i,long long end) {
	if(i!=end&&i!=3000000) {
		let(tr[i].rs,end);
		push(i);
		Rotate(i);
	}
}
void Delete(long long i,long long side) {
	
	if(tr[tr[i].ls].cnt>=side&&tr[i].ls<=cnt) {
		Delete(tr[i].ls,side);
		push(i);
		Rotate(i);
		return;
	}
	if(tr[tr[i].ls].cnt+1==side) {
		if(tr[i].ls>cnt) {
			tr[tr[i].fa].rs=tr[i].rs;
			tr[tr[i].rs].fa=tr[i].fa;
			Rotate(i);	
			return;
		}
		long long o=over(tr[i].ls); 
		if(tr[tr[i].fa].ls==i) {
			tr[tr[i].rs].fa=o;
			tr[o].rs=tr[i].rs;
			tr[tr[i].fa].ls=tr[i].ls;
			tr[tr[i].ls].fa=tr[i].fa;
			let(tr[i].ls,tr[i].rs);
		} else {
			tr[tr[i].rs].fa=o;
			tr[o].rs=tr[i].rs;
			tr[tr[i].fa].rs=tr[i].ls;
			tr[tr[i].rs].fa=tr[i].fa;
			let(tr[i].ls,tr[i].rs);
		}
		Rotate(i);
		return;
	}
	if(tr[i].cnt-tr[tr[i].rs].cnt<side) 
		Delete(tr[i].rs,side-tr[i].cnt+tr[tr[i].rs].cnt);
	push(i);
	Rotate(i);
}
char find(long long i,long long side) {
	if(tr[tr[i].ls].cnt>=side&&tr[i].ls<=cnt)
		return find(tr[i].ls,side);
	if(tr[i].cnt-tr[tr[i].rs].cnt<side) 
		return find(tr[i].rs,side-tr[i].cnt+tr[tr[i].rs].cnt);
	return tr[i].val;
}
int main() {
	int size(1<<30); 
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long t;
	long long mouse=0;
	cin>>t;
	tr[0]=(node){0,3000000,3000000,0,0};
	root=0;
	while(t--) {
		string op;
		cin>>op;
		if(op=="Move") 
			cin>>mouse;
		if(op=="Insert") {
			long long n;
			cin>>n;
			char c;
			for(int i=1;i<=n;i++) { 
				c=getchar();
				if(c=='\n') {
					i--; 
					continue; 
				}
				Insert(root,mouse+i-1,c);
			}
		}
		if(op=="Delete") {
			long long n;
			cin>>n;
			for(int i=1;i<=n;i++){
				Delete(root,mouse+1);
			}
		} 
		if(op=="Get") {
			long long n;
			cin>>n;
			for(int i=1;i<=n;i++)
				cout<<find(root,mouse+i);
			cout<<endl;
		}
		if(op=="Prev")
			mouse--;
		if(op=="Next")
			mouse++;
	}
	exit(0);
	return 0;
}