我从洛谷上把第一个测试点下下来了,跑了630ms,输出也是正确的,不知道为什么T了
#include<bits/stdc++.h>
using namespace std;
#define pushup(x) tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1
const int N = 3e6+5;
int root, idx, cur;
struct node{
char val;
int ls, rs;
int siz, pri;
} tr[N];
inline int build(char _val){
idx++;
tr[idx].val = _val;
tr[idx].siz = 1;
tr[idx].pri = rand();
return idx;
}
inline void split(int u, int x, int &L, int &R){
if( u == 0 ){
L = R = 0;
return;
}
if( tr[tr[u].ls].siz + 1 <= x ){
L = u;
split(tr[u].rs, x - tr[tr[u].ls].siz - 1, tr[u].rs, R);
}
else{
R = u;
split(tr[u].ls, x, L, tr[u].ls);
}
pushup(u);
return;
}
inline int merge(int L, int R){
if( L == 0 || R == 0 )
return L + R;
int u;
if( tr[L].pri <= tr[R].pri ){
u = L;
tr[L].rs = merge(tr[L].rs, R);
}
else{
u = R;
tr[R].ls = merge(L, tr[R].ls);
}
pushup(u);
return u;
}
inline void putout(int u){
if( !u ) return;
putout(tr[u].ls);
cout << tr[u].val;
putout(tr[u].rs);
return;
}
inline void insert(char _val){
int L, R;
split(root, cur, L, R);
root = merge(L, merge(build(_val), R));
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int m, n;
string op, s1, s2;
cin >> m;
while( m-- ){
cin >> op;
if( op == "Insert" ){
cin >> n;
int nowsiz = 0;
s1 = "", s2 = "";
while( nowsiz != n ){
getline(cin, s1);
s2 += s1;
nowsiz += s1.size();
}
for(int i = n - 1; i >= 0; i--)
insert(s2[i]);
}
if( op == "Delete" ){
cin >> n;
int L, R, l, r;
split(root, cur, L, R);
split(R, n, l, r);
root = merge(L, r);
}
if( op == "Move" ){
cin >> n;
cur = n;
}
if( op == "Prev" )
cur--;
if( op == "Next" )
cur++;
if( op == "Get" ){
cin >> n;
int L, R, l, r;
split(root, cur, L, R);
split(R, n, l, r);
putout(l);
cout << "\n";
root = merge(L, merge(l, r));
}
}
return 0;
}