显示代码纯文本
#include<cstdio>
#include<iostream>
#include<list>
#include<deque>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEB=3010;
int M;
class miku//块状链表
{
public:
int n;
char a[SIZEB];
miku(){n=0;}
void print()
{
cout<<n<<endl;
for(int i=0;i<n;i++)
printf("%c",a[i]);
cout<<endl;
}
};
list<miku> Q;
typedef list<miku>::iterator LBIND;
typedef pair<LBIND,int> BLIND;
BLIND key;
int pos=0;//光标在第几个字符
int totchar=0;//当前有多少个字符
void prin(BLIND x)
{
cout<<"first:";
miku a=*x.first;
a.print();
cout<<endl;
cout<<"second:"<<x.second<<endl;
cout<<endl;
}
void check_Q()
{
for(LBIND it=Q.begin();it!=Q.end();it++)
{
miku a=*it;
a.print();
}
}
void initalize()//插入一个空的表
{
miku tem;
Q.push_front(tem);
key.first=Q.begin();key.second=0;
pos=0;
}
void Move(int k)//将光标移动到k个字符之后
{
key.first=Q.begin();
key.second=0;
while(k>key.first->n) {k-=key.first->n,key.first++;}
key.second=k;
}
void merge(LBIND key1,LBIND key2)
{
if(key1->n+key2->n>SIZEB) return;
memcpy(key1->a+key1->n,key2->a,key2->n);
key1->n+=key2->n;
Q.erase(key2);
}
void split(LBIND key1,int k)
{
miku temp;
temp.n=key1->n-k;
memcpy(temp.a,key1->a+k,key1->n-k);
key1->n=k;
Q.insert(++key1,temp);
}
void Insert(int k)
{
if(k==0) return;
//if(k==1) prin(key);
split(key.first,key.second);
//prin(key);
miku temp;
totchar+=k;
char ch;
int best=sqrt(totchar+0.0);
LBIND now=key.first;
for(int i=1;i<=k;i++)
{
scanf("%c",&ch);
while(ch=='\n'||ch=='\r') scanf("%c",&ch);
// if(ch=='_') prin(key);
temp.a[temp.n++]=ch;
if(temp.n==best)
{
now=Q.insert(++now,temp);
temp.n=0;
}
//miku a=*now;
//if(ch=='_') check_Q();
//if(ch=='_')cout<<temp.n<<" "<<temp.a[0]<<endl;
}
if(temp.n) Q.insert(++now,temp);
//check_Q();
}
void Delete(int k)
{
if(k==0) return;
totchar-=k;
BLIND key1,key2;
key1=key;key2=key;
split(key1.first,key1.second);
while(key2.first->n-key2.second<k)
{
k-=key2.first->n-key2.second;
key2.second=0;
key2.first++;
}
key2.second+=k;
split(key2.first,key2.second);
Q.erase(++key1.first,++key2.first);
}
void get(int k)
{
BLIND key1=key;
//cout<<k<<endl;
//prin(key1);
while(key1.first->n-key1.second<k)
{
for(int i=key1.second;i<key1.first->n;i++)
{
printf("%c",key1.first->a[i]);
}
k-=key1.first->n-key1.second;
key1.second=0;
key1.first++;
}
if(k)
{
for(int i=key1.second;i<key1.second+k;i++)
printf("%c",key1.first->a[i]);
}
printf("\n");
}
void Next()
{
pos++;
key.second++;
if(key.second>key.first->n)
{
key.second=1;
key.first++;
}
}
void Prev()
{
pos--;
key.second--;
if(key.second<0)
{
key.first--;
key.second=key.first->n-1;
}
}
void keep()
{
int best=sqrt(totchar+0.1);
for(LBIND it=Q.begin();it!=Q.end();it++)
{
while(it!=Q.end()&&!Q.empty()&&it->n==0) it=Q.erase(it);
if(it==Q.end()) break;
if(it->n>2*best) split(it,best);
else
{
LBIND key2=it;key2++;
if(key2==Q.end()) continue;
if(it->n+key2->n<=best) merge(it,key2);
}
}
if(Q.empty()) initalize();
}
int main()
{
freopen("editor2003.in","r",stdin);
freopen("editor2003.out","w",stdout);
scanf("%d",&M);
initalize();
int p;
string r;
for(int i=1;i<=M;i++)
{
cin>>r;
//cout<<r<<endl;
if(r=="Move"||r=="Delete"||r=="Insert"||r=="Get") scanf("%d",&p);
if(r=="Move") {pos=p;Move(p);}
else if(r=="Insert") Insert(p);
else if(r=="Delete") Delete(p);
else if(r=="Get") get(p);
else if(r=="Next") Next();
else if(r=="Prev") Prev();
else cout<<"error"<<endl;
if(r=="Insert"||r=="Delete")
{
//check_Q();
//cout<<pos<<endl;
keep();
//cout<<"arrive2"<<endl;
Move(pos);
//cout<<"***************"<<endl;
}
}
return 0;
}