C++14(g++5.4) 解法, 执行用时: 1381ms, 内存消耗: 39040K, 提交时间: 2019-06-11 14:21:30

#include<bits/stdc++.h>
#define MAXN 2000010
#define LL long long int
#define FIO ios::sync_with_stdio(false)
#define FRD freopen("input.txt","r",stdin)
const LL MOD=1e9+10;
using namespace std;
int f[MAXN],cnt[MAXN],ch[MAXN][2],size[MAXN],sz,rt,pt=0;
char key[MAXN];
void clear(int x){
    f[x]=cnt[x]=ch[x][0]=ch[x][1]=size[x]=key[x]=0;
}
bool get(int x){
    return ch[f[x]][1]==x;
}
void pushup(int x){
    if (x){
        size[x]=cnt[x];
        if (ch[x][0]) size[x]+=size[ch[x][0]];
        if (ch[x][1]) size[x]+=size[ch[x][1]];
    }
}
void rotate(int x){
    int old=f[x],oldf=f[old],which=get(x);
    ch[old][which]=ch[x][which^1]; f[ch[old][which]]=old; 
    ch[x][which^1]=old; f[old]=x;
    f[x]=oldf;
    if (oldf) ch[oldf][ch[oldf][1]==old]=x;
    pushup(old); pushup(x);
}
void splay(int x){
    for (int fa; fa=f[x]; rotate(x))
        if (f[fa])
            rotate((get(x)==get(fa))?fa:x);
    rt=x;
}
void insert(char x){
	if(rt==0){
		sz++;key[sz]=x;rt=sz;
		cnt[sz]=size[sz]=1;
		f[sz]=ch[sz][1]=ch[sz][0]=0;
		return;
	}
	sz++;
	ch[sz][1]=ch[rt][1];f[ch[rt][1]]=sz;
	ch[rt][1]=sz;f[sz]=rt;
	cnt[sz]=1;
	key[sz]=x;
	pushup(sz);pushup(rt);
}
int kth(int x){
    int now=rt;
    while (1){
        if (ch[now][0] && x<=size[ch[now][0]])
            now=ch[now][0];
        else{
            int temp=size[ch[now][0]]+cnt[now];
            if (x<=temp)
                return now;
            x-=temp; now=ch[now][1];
        }
    }
}
int pre(){
    int now=ch[rt][0];
    while (ch[now][1]) now=ch[now][1];
    return now;
}
int next(){
    int now=ch[rt][1];
    while (ch[now][0]) now=ch[now][0];
    return now;
}
void del(){
    if (cnt[rt]>1) {cnt[rt]--; pushup(rt); return;}
    if (!ch[rt][0] && !ch[rt][1]) {clear(rt); rt=0; return;}
    if (!ch[rt][0]) {
        int oldrt=rt; rt=ch[rt][1]; f[rt]=0; clear(oldrt); return;
    }
    else if (!ch[rt][1]) {
        int oldrt=rt; rt=ch[rt][0]; f[rt]=0; clear(oldrt); return;
    }
    int oldrt=rt; int leftbig=pre();
    splay(leftbig);
    ch[rt][1]=ch[oldrt][1];
    f[ch[oldrt][1]]=rt;
    clear(oldrt);
    pushup(rt);
}
void init(){
	for(int i=1;i<=sz;i++)
		clear(i);
	sz=0;
	rt=0;
}
void MOVE(int k){
	pt=kth(k+1);
}
void DELETE(int n){
	splay(pt);
	for(int i=0;i<n;i++){
		splay(next());
		//cout<<key[rt]<<endl;
		del();
	}
}
void GET(int n){
	splay(pt);
	for(int i=0;i<n;i++){
		splay(next());
		cout<<key[rt];
	}
	cout<<endl;
}
void PREV(){
	splay(pt);
	pt=pre();
}
void NEXT(){
	splay(pt);
	pt=next();
}
void INSERT(string &str){
	splay(pt);
	for(int i=str.size()-1;i>=0;i--){
		insert(str[i]);
	}
}
int main(){
	//FRD;
	FIO;
	insert('!');
	insert('$');
	pt=1;
	int q;
	cin>>q;
	while(q--){
		string str;
		cin>>str;
		if(str=="Insert"){
			int n;
			cin>>n;
			splay(pt);
			int tot=0;
			string str="";
			while(tot<n){
				string tmp;
				getline(cin,tmp);
				tot+=tmp.size();
				str+=tmp;
			}
			INSERT(str);
		}
		else if(str=="Move"){
			int n;
			cin>>n;
			MOVE(n);
		}
		else if(str=="Delete"){
			int n;
			cin>>n;
			DELETE(n);
		}
		else if(str=="Next"){
			NEXT();
		}
		else if(str=="Prev"){
			PREV();
		}
		else if(str=="Get"){
			int n;
			cin>>n;
			GET(n);
		}
		//cout<<key[pt]<<endl;
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1294ms, 内存消耗: 22984K, 提交时间: 2022-09-29 23:39:19

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ext/rope>

using namespace __gnu_cxx;
using namespace std;

rope <char> editor;

char ch;
string oper;
int pos, n, rela;

int main(){
	cin.tie(0);
	cout.tie(0);
	
	scanf("%d", &n);
	
	while(n--){
	    cin >> oper;
	    scanf("%d", &rela);
	    
		if(oper =="Insert"){
		    int pos1 = pos;
			while(rela){
				ch = getchar();
				if((int)ch >= 32 && (int)ch <= 126){
				    editor.insert(pos1, ch);
				    rela--;
				    pos1++;
				}
			}
        }
        else if(oper =="Move") pos = rela;
        else if(oper =="Next") pos++;
        else if(oper =="Prev") pos--;
        else if(oper =="Get") cout << editor.substr(pos, rela) << endl;
        else if(oper =="Delete") editor.erase(pos, rela);
	}
	return 0;
}