「Editor」

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cctype> #include <cstring> #include <string> #define MAXIN 1 #define gc() (SS == TT && (TT = (SS = IN) + fread(IN,1,MAXIN,stdin),SS == TT) ? -1 : *SS++) int N, qqq; const int M = 1024 * 1024 * 1 + 5; int maxsize = 40000, maxnum; int num, *next, *sz, *pool; char **data, str[M], IN[MAXIN], *SS = IN, *TT = IN; char *pre; inline int read() { int now = 0, f = 1; register char c = gc(); for (; !isdigit(c); c = gc()) if (c == '-') f = -1; for (; isdigit(c); now = now * 10 + c - '0', c = gc()); return now * f; } inline int new_block() { return pool[++num]; } inline void del_block(int v) { pool[num--] = v; } void init() { for (int i = 1; i < maxnum; ++i) pool[i] = i; sz[0] = 0; //新建一个0节点，方便 表头就是0 next[0] = -1; } void merge(int cur, int Next) { memcpy(data[cur] + sz[cur], data[Next], sz[Next]); next[cur] = next[Next]; sz[cur] += sz[Next]; del_block(Next); } void maintain() { for (int cur = 0, Next = next[0]; ~cur; cur = next[cur], Next = next[cur]) while ((~Next) && sz[cur] + sz[Next] <= maxsize) { merge(cur, Next);//最好不用next[Next]，因为已经合并、删掉了 Next = next[cur]; } } int get_index(int &pos) //找到pos所在的块，并将pos定位为块内位置 { int cur = 0; while ((~cur) && pos > sz[cur]) //把cur定位到某一块的末尾，不用下一块开头了(pos>=sz) { pos -= sz[cur]; cur = next[cur]; } return cur; } void update(int cur, int Next, int len, char *s)//给新的块Next设置数据及指针 { next[Next] = next[cur]; next[cur] = Next; sz[Next] = len; memcpy(data[Next], s, len); } void split(int cur, int pos) { if (cur == -1 || pos == sz[cur])//不能判!pos 因为后边会直接用next[cur]，不分裂会跳过该块 return; int Next = new_block(); update(cur, Next, sz[cur] - pos, data[cur] + pos); sz[cur] = pos; } void insert(int pos, int len) { int cur = get_index(pos), sum = 0, Next; split(cur, pos); while (sum + maxsize <= len) { Next = new_block(); update(cur, Next, maxsize, str + sum);//先分成尽可能多的整块 sum += maxsize; cur = Next; } if (len - sum) //剩余的单独放到一块 Next = new_block(), update(cur, Next, len - sum, str + sum); maintain(); } void erase(int pos, int len) { int cur = get_index(pos), Next; split(cur, pos); Next = next[cur]; //because of here while ((~Next) && len > sz[Next]) len -= sz[Next], del_block(Next), Next = next[Next]; split(Next, len); del_block(Next), next[cur] = next[Next]; maintain(); } void get_data(int pos, int len) { delete[]pre; int cur = get_index(pos), sum = sz[cur] - pos; if (len < sum) sum = len; //memcpy(str, data[cur] + pos, sum); fwrite(data[cur] + pos, sizeof(char), sum, stdout); cur = next[cur]; while ((~cur) && sum + sz[cur] <= len) { //memcpy(str + sum, data[cur], sz[cur]); fwrite(data[cur], sizeof(char), sz[cur], stdout); sum += sz[cur]; cur = next[cur]; } if ((~cur) && len - sum) fwrite(data[cur], sizeof(char), len - sum, stdout); //memcpy(str + sum, data[cur], len - sum); //str[len] = '\0'; //printf("%s", str); } bool alloc(int size) { next = new(std::nothrow) int[size]; if (next == NULL) return false; sz = new(std::nothrow) int[size]; if (sz == NULL) return false; pool = new(std::nothrow) int[size]; if (pool == NULL) return false; data = new(std::nothrow) char*[size]; if (data == NULL) return false; for (int i = 0; i < size; ++i) { data[i] = new(std::nothrow) char[maxsize]; qqq = i; if (data[i] == NULL) return false; } return true; } int main() { freopen("input.txt", "rb", stdin); freopen("output.txt", "wb", stdout); fseek(stdin, 0L, SEEK_END); N = ftell(stdin); fseek(stdin, 0L, SEEK_SET); maxnum = N * 2 / maxsize + 100; pre = new(std::nothrow) char[M]; int left = 1, right = maxnum, mid = (left + right) / 2; while (1) { if (left == mid || right == mid) { maxnum = mid; break; } if (alloc(mid) == true) { delete[]next; delete[]sz; delete[]pool; for (int i = 0; i < mid; ++i) delete[]data[i]; delete[]data; left = mid; mid = (left + right) / 2; } else { delete[]next; delete[]sz; delete[]pool; for (int i = 0; i < qqq; ++i) delete[]data[i]; delete[]data; right = mid; mid = (left + right) / 2; } } alloc(maxnum); int limit; if (maxnum > 200) limit = (maxnum - 100)*maxsize / 2; else limit = 100 * maxsize / 2; init(); int pos = 0, len, tot = 0; char c; while (1) { c = gc(); if (c == -1) break; if (c == 'a') { len = read(); if (len + tot > limit) { get_data(0, tot); return 0; } while (1) { char ch = gc(); if (isdigit(ch) || islower(ch) || isupper(ch)) { str[0] = ch; break; } } fread(str + 1, sizeof(char)*(len - 1), 1, stdin); insert(tot, len); tot += len; //get_data(0, tot); while (gc() != '\n') ; } else if (c == 'i') { pos = read(); len = read(); if (len + tot > limit) { get_data(0, tot); return 0; } while (1) { char ch = gc(); if (isdigit(ch) || islower(ch) || isupper(ch)) { str[0] = ch; break; } } fread(str + 1, sizeof(char), len - 1, stdin); insert(pos - 1, len); tot += len; //get_data(0, tot); while (gc() != '\n') ; } else if (c == 'd') { pos = read(); len = read(); erase(pos - 1, len); tot -= len; //get_data(0, tot); } else if (c == 'r') { pos = read(); len = read(); erase(pos - 1, len); tot -= len; len = read(); if (len + tot > limit) { get_data(0, tot); return 0; } tot += len; while (1) { char ch = gc(); if (isdigit(ch) || islower(ch) || isupper(ch)) { str[0] = ch; break; } } fread(str + 1, sizeof(char), len - 1, stdin); insert(pos - 1, len); //get_data(0, tot); while (gc() != '\n') ; } else if (c == '#') while (gc() != '\n') ; } get_data(0, tot); fclose(stdout); fclose(stdin); return 0; }