【BZOJ1507】【NOI2003】Editor

  Splay，敲完就好了。

  坑爹的换行符竟然是不读入的...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=3000010;

struct Splay_Tree
{
	struct Node
	{
		Node *c[2],*p;
		char v;
		int tag_rev;
		int size;
		int w() {return this==p->c[1];}
	}MEM[maxn],*Null,*root;
	int IDs;

	#define ls x->c[0]
	#define rs x->c[1]

	Node* NewNode()
	{
		Node *x=&MEM[IDs++];
		ls=rs=x->p=Null;
		x->v=0;x->size=1;
		return x;
	}

	Splay_Tree()
	{
		Null=&MEM[0];
		Null->v=Null->size=0;
		Null->c[0]=Null->c[1]=Null->p=Null;
		IDs=1;
		Node *LeftNull=NewNode();
		Node *RightNull=NewNode();
		root=LeftNull;
		root->c[1]=RightNull;RightNull->p=root;root->size=2;
	}

	void Update(Node *x) {if (x==Null) return;x->size=ls->size+rs->size+1;}

	void Mark_Rev(Node *x) {swap(ls,rs);x->tag_rev^=1;}

	void Push_Down(Node *x)
	{
		if (x==Null) return;
		if (x->tag_rev)
		{
			Mark_Rev(ls);
			Mark_Rev(rs);
			x->tag_rev=0;
		}
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		Push_Down(p);Push_Down(x);
		if (p==root) root=x;
		x->p=p->p;p->p->c[p->w()]=x;
		x->c[!w]->p=p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x,Node *top)
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=top)
		{
			if (x->p->p==top) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	Node* Select(int k)
	{
		Node *x=root;
		while (k)
		{
			Push_Down(x);
			int lsz=ls->size;
			if (lsz+1==k) return x;
			else if (lsz>=k) x=ls;
			else k-=lsz+1,x=rs;
		}
	}

	Node* Build_Tree(int l,int r,char *ch)
	{
		Node *x=NewNode();
		if (l==r) {x->v=ch[l];return x;}
		int mid=(l+r)>>1;
		x->v=ch[mid];
		if (l<mid) ls=Build_Tree(l,mid-1,ch);
		if (mid<r) rs=Build_Tree(mid+1,r,ch);
		ls->p=rs->p=x;
		Update(x);
		return x;
	}

	Node* Get_Seq(int l,int r)
	{
		Splay(Select(l-1),Null);
		Splay(Select(r+1),root);
		return root->c[1]->c[0];
	}

	void Print(Node *x)
	{
		if (x==Null) return;
		Print(ls);
		putchar(x->v);
		Print(rs);
	}
	
	void Insert(int pos,int n,char *ch)
	{
		Node *NewRoot=Build_Tree(1,n,ch);
		Splay(Select(pos),Null);
		Splay(Select(pos+1),root);
		root->c[1]->c[0]=NewRoot;
		NewRoot->p=root->c[1];
		Splay(NewRoot,Null);
	}
	
	void Delete(int pos,int n)
	{
		Node *x=Get_Seq(pos+1,pos+n);
		x->p->c[x->w()]=Null;
		Update(x->p);
		Splay(x->p,Null);
	}
	
	void Rotate(int pos,int n)
	{
		Node *x=Get_Seq(pos+1,pos+n);
		Mark_Rev(x);
		Splay(x,Null);
	}

	void Print(int pos,int n)
	{
		Node *x=Get_Seq(pos+1,pos+n);
		Print(x);
		Splay(x,Null);
	}
}T;

char readchar() {char ch;while ((ch=getchar())<32 || ch>126 || ch=='\n');return ch;}

char inst[maxn];

int main()
{
	int TT,pos=0,n;
	scanf("%d",&TT);
	while (TT--)
	{
		char ctr[10];
		scanf("%s",ctr);
		if (ctr[0]=='M') scanf("%d",&n),pos=n;
		else if (ctr[0]=='I')
		{
			scanf("%d",&n);
			for (int i=1;i<=n;i++) inst[i]=readchar();
			T.Insert(pos+1,n,inst);
		}
		else if (ctr[0]=='D') scanf("%d",&n),T.Delete(pos+1,n);
		else if (ctr[0]=='G') scanf("%d",&n),T.Print(pos+1,n),putchar('\n');
		else if (ctr[0]=='P') pos--;
		else if (ctr[0]=='N') pos++;
		else if (ctr[0]=='R') scanf("%d",&n),T.Rotate(pos+1,n);
	}
	return 0;
}

  听说一个rope就好了，我就写了一下。

#include <cstdio>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int maxn=3000010;

char readchar() {char ch;while ((ch=getchar())<32 || ch>126 || ch=='\n');return ch;}

char ch[maxn];
char ctr[20];
crope text;

int main()
{
	int T;
	scanf("%d",&T);
	int pos=0,n;
	while (T--)
	{
		scanf("%s",ctr);
		if (ctr[0]=='M') scanf("%d",&n),pos=n;
		else if (ctr[0]=='I')
		{
			scanf("%d",&n);
			for (int i=0;i<n;i++) ch[i]=readchar();
			ch[n]=0;
			text.insert(pos,ch);
		}
		else if (ctr[0]=='P') pos--;
		else if (ctr[0]=='N') pos++;
		else if (ctr[0]=='D') scanf("%d",&n),text.erase(pos,n);
		else if (ctr[0]=='G') scanf("%d",&n),text.copy(pos,n,ch),ch[n]=0,printf("%s\n",ch); 
	}
	return 0;
}