problem
传送门
Solution
块状链表板子题……
码了一下午，调了一晚上，代码重构了3遍，在终于过了。
还是太菜了。
移动光标的操作直接模拟即可。
插入操作，先将光标所在块分裂成两块，然后直接插入。
删除操作直接将边角料变成新块，然后相互连接。
细节有点多……
第一次打，代码奇丑，而且没有优化空间……
算了，以后在填坑吧……
Code
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> 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<int, int> 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('\n');
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('\n');
}
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_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
int 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;
}
转载于:https://www.cnblogs.com/LZYcaiji/p/10397865.html
相关资源：NOI2003试题day1
