记录编号	90296	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.603 s
提交时间	2014-03-07 17:13:45	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<list>
using namespace std;
const int SIZEB=3000;
class BLOCK{
public:
	int n;
	char a[SIZEB];
	BLOCK(){n=0;}
	void print(void){
		cout<<"size:"<<n<<endl;
		for(int i=1;i<=n;i++) cout<<a[i];cout<<endl;
	}
};
list<BLOCK> lis;//块状链表
int totchar=0;
typedef list<BLOCK>::iterator LISIND;//指向链表的指针
typedef pair<LISIND,int> BLIND;//指向块状链表的指针
BLIND cursor;
int crpos=0;
BLIND lisbegin(void){
	BLIND ans;
	ans.first=lis.begin();
	ans.second=0;
	return ans;
}
void initalize(void){//向lis里面放一个不含元素的块
	BLOCK t;
	lis.push_front(t);
	cursor=lisbegin();
	crpos=0;
}
void print(LISIND x){//调试接口,输出该迭代器指向的地址
	BLOCK *a=&(*x);
	cout<<a;
}
void print(BLIND x){//调试接口,输出该指针指向的位置
	print(x.first);
	cout<<" "<<x.second;
}
void printbl(void){//调试接口,输出块状链表
	LISIND key;
	printf("Contain %d blocks:\n",lis.size());
	for(key=lis.begin();key!=lis.end();key++){
		cout<<"pos:";
		print(key);cout<<endl;
		key->print();
	}
}
void printblsize(void){//调试接口,输出块状链表每一块的大小
	printf("Contain %d blocks:\n",lis.size());
	LISIND key;
	for(key=lis.begin();key!=lis.end();key++){
		cout<<key->n<<" ";
	}
	cout<<endl;
}
void split(LISIND x,int former){//将x分裂,前一块的大小是former
	BLOCK lat;
	memcpy(lat.a+1,x->a+former+1,x->n-former);
	lat.n=x->n-former;
	x->n=former;
	lis.insert(++x,lat);
}
void merge(LISIND x,LISIND y){//把y接到x后面
	if(y->n+x->n>=SIZEB) return;//合起来的块过大了
	memcpy(x->a+x->n+1,y->a+1,y->n);
	x->n+=y->n;
	lis.erase(y);
}
void keepbalance(void){//保持块状链表每一块的大小都比较"正常"
	int best=sqrt(totchar+0.0);
	for(LISIND key1=lis.begin();key1!=lis.end();key1++){
		while(key1!=lis.end()&&!lis.empty()&&key1->n==0) key1=lis.erase(key1);
		if(key1==lis.end()) break;
		if(key1->n>2*best) split(key1,best);
		else{
			LISIND key2=key1;key2++;
			if(key2==lis.end()) continue;
			if(key1->n+key2->n<=best) merge(key1,key2);
		}
	}
	if(lis.empty()) initalize();
}
void Move(int k){//定位
	cursor=lisbegin();
	while(k>cursor.first->n) k-=cursor.first->n,cursor.first++;
	cursor.second=k;
}
void Insert(int s){//光标后插入长度为s的字符串
	if(s==0) return;
	split(cursor.first,cursor.second);
	BLOCK temp;
	totchar+=s;
	int best=sqrt(totchar+0.0);
	LISIND now=cursor.first;
	for(int i=1;i<=s;i++){
		char ch;scanf("%c",&ch);
		while(ch=='\n'||ch=='\r') scanf("%c",&ch);
		temp.a[++temp.n]=ch;
		if(temp.n==best){
			now=lis.insert(++now,temp);
			temp.n=0;
		}
	}
	if(temp.n) lis.insert(++now,temp);
}
void Delete(int s){//删除光标后的s个字符
	if(s==0) return;
	totchar-=s;
	BLIND key1,key2;
	key1=cursor;key2=key1;
	split(key1.first,key1.second);
	while(key2.first->n-key2.second<s) s-=(key2.first->n-key2.second),key2.first++,key2.second=0;
	key2.second+=s;
	split(key2.first,key2.second);
	lis.erase(++key1.first,++key2.first);
}
void Prev(void){//光标前移一个字符
	crpos--;
	if(cursor.second==0){
		cursor.first--;
		cursor.second=cursor.first->n-1;
	}
	else cursor.second--;
}
void Next(void){//光标后移一个字符
	crpos++;
	if(cursor.second==cursor.first->n){
		cursor.first++;
		cursor.second=1;
	}
	else cursor.second++;
}
void Get(int s){//输出光标后的s个字符
	BLIND key=cursor;
	while(s){
		while(s&&key.second<key.first->n)	printf("%c",key.first->a[++key.second]),s--;
		if(s) key.first++,key.second=0;
	}
	printf("\n");
}
int main(void){
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	initalize();
	int Q;
	scanf("%d",&Q);
	string cmd;
	int s;
	LISIND key=lis.begin();
	while(Q--){
		cin>>cmd;
		if(cmd=="Insert"||cmd=="Move"||cmd=="Delete"||cmd=="Get") scanf("%d",&s);
		if(cmd=="Insert") Insert(s);
		else if(cmd=="Move") crpos=s,Move(crpos);
		else if(cmd=="Delete") Delete(s);
		else if(cmd=="Get")	Get(s);
		else if(cmd=="Next") Next();
		else if(cmd=="Prev") Prev();
		if(cmd=="Insert"||cmd=="Delete"){//仅有两个改变链表的操作
			keepbalance();
			Move(crpos);
		}
	}
	return 0;
}