传送门（JZOJ）
（第一道全国决赛题）
解法 1：使用 Splay 维护
不管怎么说，总和刚刚学过的迎合上了。这道题可以直接上 Splay 维护线性序列，光标位置用一个变量存就可以了。
这次写 Splay 时犯的错误：
1.一个地方的 null 写成了 NULL
就没有了。
但是最后有一个点 Runtime Error 了，经调试，发现是 select 时栈溢出了，说明 Splay 退化成了一条链。但是这个测试点操作并不多，一开始我还建成了一棵完全二叉树，为什么会溢出呢？
数据大概长这样
Insert 2 ^ 20
Delete 2 ^ 20
观察发现，我的输出字符串是通过不断地旋转根结点寻找后继来输出的，因为这个时间是 O(1) 的，所以我就这么写了。栈溢出，说明这样从头到尾 select 后，Splay 退化成了链状。以后可不能这么遍历序列了。
正确的做法是：把中间要输出的序列 split 出来，中序遍历后再 merge。这样就能防止退化了。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
typedef int INT;
using std::cin;
using std::cout;
using std::endl;
inline INT readIn()
{
INT a = 0;
bool minus = false;
char ch = getchar();
while (!(ch == '-' || (ch >= '0' && ch <= '9'))) ch = getchar();
if (ch == '-')
{
minus = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
a = a * 10 + (ch - '0');
ch = getchar();
}
if (minus) a = -a;
return a;
}
inline void printOut(INT x)
{
char buffer[20];
INT length = 0;
bool minus = x < 0;
if (minus) x = -x;
do
{
buffer[length++] = x % 10 + '0';
x /= 10;
} while (x);
if (minus) buffer[length++] = '-';
do
{
putchar(buffer[--length]);
} while (length);
}
INT q;
class Splay
{
struct Node
{
char v;
INT s;
Node* ch[2];
Node() : v(), s(), ch() {}
void maintain()
{
s = ch[0]->s + ch[1]->s + 1;
}
INT comp(INT k)
{
if (k == ch[0]->s + 1) return -1;
return ch[0]->s + 1 < k;
}
};
Node *null;
Node *root;
public:
Splay()
{
null = new Node;
null->ch[0] = null->ch[1] = null;
root = new Node;
root->ch[1] = new Node;
root->ch[0] = root->ch[1]->ch[0] = root->ch[1]->ch[1] = null;
root->ch[1]->maintain();
root->maintain();
}
private:
void rotate(Node* &r, INT d)
{
Node* k = r->ch[d ^ 1];
r->ch[d ^ 1] = k->ch[d];
k->ch[d] = r;
r->maintain();
k->maintain();
r = k;
}
void select(Node* &r, INT k)
{
INT d = r->comp(k);
if (d == -1) return;
INT k1 = k - d * (r->ch[0]->s + 1);
Node* &p = r->ch[d];
INT d2 = p->comp(k1);
INT k2 = k1 - d2 * (p->ch[0]->s + 1);
if (d2 != -1)
{
select(p->ch[d2], k2);
if (d == d2)
rotate(r, d ^ 1);
else
rotate(p, d2 ^ 1);
}
rotate(r, d ^ 1);
}
public:
void wander(INT l, INT r)
{
Node* mid = split(root, l + 1);
Node* right = split(mid, r - l + 1);
wander(mid);
merge(root, merge(mid, right));
}
private:
void wander(Node* r)
{
if (r == null) return;
wander(r->ch[0]);
putchar(r->v);
wander(r->ch[1]);
}
private:
Node* split(Node* &r, INT k)
{
select(r, k);
Node* ret = r->ch[1];
r->ch[1] = null;
r->maintain();
return ret;
}
Node* merge(Node* &l, Node* r)
{
select(l, l->s);
l->ch[1] = r;
l->maintain();
return l;
}
public:
void erase(INT l, INT r)
{
Node* mid = split(root, l + 1);
Node* right = split(mid, r - l + 1);
merge(root, right);
}
public:
void insert(char* str, INT k)
{
INT length = strlen(str);
Node* ins = null;
make(ins, 0, length, str);
Node* right = split(root, k + 1);
merge(root, merge(ins, right));
}
private:
void make(Node* &node, INT l, INT r, char* str)
{
if (l >= r) return;
node = new Node;
node->ch[0] = node->ch[1] = null;
INT mid = (l + r) >> 1;
node->v = str[mid];
make(node->ch[0], l, mid, str);
make(node->ch[1], mid + 1, r, str);
node->maintain();
}
};
char buffer[2 * 1024 * 1024 + 5];
void run()
{
q = readIn();
Splay editor;
INT pos = 0;
while (q--)
{
char ins[10];
scanf("%s", ins);
switch (ins[0])
{
case 'M':
{
pos = readIn();
break;
}
case 'I':
{
INT length = readIn();
for (int i = 0; i < length; i++)
{
char ch = getchar();
while (!(ch >= 32 && ch <= 126)) ch = getchar();
buffer[i] = ch;
}
buffer[length] = '\0';
editor.insert(buffer, pos);
break;
}
case 'D':
{
INT length = readIn();
editor.erase(pos, pos + length - 1);
break;
}
case 'G':
{
INT length = readIn();
editor.wander(pos, pos + length - 1);
putchar('\n');
break;
}
case 'P':
{
pos--;
break;
}
case 'N':
{
pos++;
break;
}
default:
break;
}
}
}
int main()
{
run();
return 0;
}
解法 2：使用块状链表维护
块状链表的使用详细见专题，这里只贴个代码（C++ 11）
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <bitset>
typedef int INT;
using std::cin;
using std::cout;
using std::endl;
inline INT readIn()
{
INT a = 0;
bool minus = false;
char ch = getchar();
while (!(ch == '-' || (ch >= '0' && ch <= '9'))) ch = getchar();
if (ch == '-')
{
minus = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
a = a * 10 + (ch - '0');
ch = getchar();
}
if (minus) a = -a;
return a;
}
inline void printOut(INT x)
{
char buffer[20];
INT length = 0;
bool minus = x < 0;
if (minus) x = -x;
do
{
buffer[length++] = x % 10 + '0';
x /= 10;
} while (x);
if (minus) buffer[length++] = '-';
do
{
putchar(buffer[--length]);
} while (length);
}
class BlockList
{
static const INT size = 5000;
struct Block
{
INT s;
char v[size];
Block() : s() {}
Block(char* begin, char* end) : s(), v()
{
s = end - begin;
std::copy(begin, end, v);
}
};
std::list<Block> blocks;
typedef std::list<Block>::iterator IT;
static IT Next(IT it) { IT ret = it; return ++ret; }
IT locate(INT& k)
{
IT it;
for (it = blocks.begin(); it != blocks.end(); it++)
{
if (k <= it->s)
return it;
k -= it->s;
}
return it;
}
void maintain()
{
IT it;
for (it = blocks.begin(); it != blocks.end(); it++)
{
IT next = Next(it);
while (next != blocks.end() && it->s + next->s <= size)
{
merge(it, next);
next = Next(it);
}
}
}
void merge(IT l, IT r)
{
std::copy(r->v, r->v + r->s, l->v + l->s);
l->s += r->s;
blocks.erase(r);
}
bool split(IT it, INT k)
{
if (k >= it->s) return false;
blocks.insert(Next(it), Block(it->v + k, it->v + it->s));
it->s = k;
return true;
}
public:
void insert(char* begin, char* end, INT k)
{
IT it = locate(k);
if (it != blocks.end())
{
split(it, k);
it++;
}
while (end - begin >= size)
{
blocks.insert(it, Block(begin, begin + size));
begin += size;
}
if (end - begin)
{
blocks.insert(it, Block(begin, end));
}
maintain();
}
void erase(INT k, INT s)
{
IT it = locate(k);
split(it, k);
it++;
IT next = it;
while (s > 0)
{
next++;
if (it->s < s)
{
s -= it->s;
blocks.erase(it);
}
else
{
split(it, s);
s -= it->s;
blocks.erase(it);
}
it = next;
}
maintain();
}
typedef void(*Func)(const char& v);
void wander(INT k, INT s, Func op)
{
IT it = locate(k);
k--;
while (s--)
{
op(it->v[k++]);
if (k >= it->s)
{
it++;
k = 0;
}
}
}
};
char buffer[2 * 1024 * 1024 + 5];
void run()
{
INT q = readIn();
BlockList editor;
INT pos = 0;
while (q--)
{
char ins[10];
scanf("%s", ins);
switch (ins[0])
{
case 'M':
{
pos = readIn();
break;
}
case 'I':
{
INT length = readIn();
for (int i = 0; i < length; i++)
{
char ch = getchar();
while (!(ch >= 32 && ch <= 126)) ch = getchar();
buffer[i] = ch;
}
editor.insert(buffer, buffer + length, pos);
break;
}
case 'D':
{
INT length = readIn();
editor.erase(pos, length);
break;
}
case 'G':
{
INT length = readIn();
editor.wander(pos + 1, length, [](const char& ch) { putchar(ch); });
putchar('\n');
break;
}
case 'P':
{
pos--;
break;
}
case 'N':
{
pos++;
break;
}
default:
break;
}
}
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
