problem
传送门
Solution
块状链表板子题……
码了一下午，调了一晚上，代码重构了3遍，在终于过了。
还是太菜了。
移动光标的操作直接模拟即可。
插入操作，先将光标所在块分裂成两块，然后直接插入。
删除操作直接将边角料变成新块，然后相互连接。
细节有点多……
第一次打，代码奇丑，而且没有优化空间……
算了，以后在填坑吧……
Code
#include using namespace std;#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd secondtemplate inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }inline int read(){int res = 0, fl = 1;char r = getchar();for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;return res * fl;
}
typedef long long LL;
typedef pair pii;const int Maxl = 1024 * 1024 * 2, siz = Maxl / 500, blk = Maxl / siz;
char ch[Maxl + 10];
int cnt;struct node {int lst, nxt, len;short c[blk + 10];void putout(){ for (int i = 1; i <= len; ++i) putchar(c[i]);}void back(int C){ c[++len] = C;}
}B[siz << 6];
void check(){for (int id = 1; B[id].nxt; id = B[id].nxt){if(B[B[id].nxt].len + B[id].len <= blk){for (int i = 1; i <= B[B[id].nxt].len; ++i)B[id].back(B[B[id].nxt].c[i]);B[id].nxt = B[B[id].nxt].nxt;B[B[id].nxt].lst = id;}}
}
int find(int cur, int &Id){for (Id = 1; Id && cur > B[Id].len; Id = B[Id].nxt) cur -= B[Id].len;return cur;
}
void MakeBlock(int len,int Lst){int num = 1;B[++cnt].lst = Lst;B[Lst].nxt = cnt;for (int i = 1; i <= len; ++i){if(num * blk + 1 == i){B[cnt].nxt = cnt + 1;cnt++, num++;B[cnt].lst = cnt - 1;}B[cnt].back(ch[i]);}
}
char tmp[5000];
void Insert(int cur, int len){int Id;cur = find(cur, Id);int Nxt = B[Id].nxt, Lst = B[Id].lst;MakeBlock(len, Id);for (int i = 1; i <= B[Id].len - cur; ++i) ch[i] = B[Id].c[cur + i];MakeBlock(B[Id].len - cur, cnt);B[cnt].nxt = Nxt;B[Nxt].lst = cnt;B[Id].len = cur;check();
}
void put_out(int cur,int len){int Bid, Eid, ecur;ecur = find(cur + len, Eid);cur = find(cur, Bid);if(Bid == Eid){for (int i = cur + 1; i <= ecur; ++i) putchar(B[Bid].c[i]);putchar('
');return;}for (int i = cur + 1; i <= B[Bid].len; ++i)putchar(B[Bid].c[i]);for (Bid = B[Bid].nxt; Bid != Eid; Bid = B[Bid].nxt)B[Bid].putout();for (int i = 1; i <= ecur; ++i) putchar(B[Bid].c[i]);putchar('
');
}
void Erase(int cur, int len){int Bid, Eid, ecur;ecur = find(cur + len, Eid);cur = find(cur, Bid);if(Bid == Eid){int xz = 0;for (int i = 1; i <= cur; ++i) ch[++xz] = B[Bid].c[i];for (int i = ecur + 1; i <= B[Bid].len; ++i) ch[++xz] = B[Bid].c[i];for (int i = 1; i <= xz; ++i) B[Bid].c[i] = ch[i];B[Bid].len = xz;check();return ;}B[Bid].len = cur;int xz = 0;for (int i = ecur + 1; i <= B[Eid].len; ++i) B[Eid].c[++xz] = B[Eid].c[i];B[Eid].len = xz;B[Bid].nxt = Eid;B[Eid].lst = Bid;check();
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin);freopen("a.out", "w", stdout);
#endifint t = read(), cur = 0;char opt[10];MakeBlock(blk, 0);while(t--){scanf("%s",opt + 1);if(opt[1] == 'M') cur = read();if(opt[1] == 'P') cur--;if(opt[1] == 'N') cur++;if(opt[1] == 'D') Erase(cur, read());if(opt[1] == 'G') put_out(cur, read());if(opt[1] == 'I'){int len = read();for (int i = 1; i <= len; ++i){ch[i] = getchar();if(ch[i] < 32 || ch[i] > 126) i--;}Insert(cur, len);}}return 0;
}