2
22
2016
0

[BZOJ1269] [AHOI2006]文本编辑器editor

这题写了我1.5h……

以后写题目必须认真、仔细!

Pushdown居然写错了……调试了半天

所以以后必须仔细想好细节再写,这样才能节省时间。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,move_to=0;
char s[2000005];

struct Node{
char v;
int rev,siz;
Node *ch[2],*fa;
Node(char ch,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(char c,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
v=c;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else {Rotate(y,1);Rotate(x,1);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(k==splay->ch[0]->siz+1)return splay;
if(k<=splay->ch[0]->siz)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos),*y=Find(root,pos+tot+1);
Splay(x,Null);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(s[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

Node *GetNull(){
Node *p=new Node('#',Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=p->rev=0;
}

void Build_First(){
Null=GetNull();
s[1]='H';
s[2]='i';
root=Build(1,2);
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

void Delete(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}

char GetKey(int pos){
Node *u=Split(pos,1);
return u->v;
}

void GetString(int len){
char ch;
while((ch=getchar())=='\n');
s[1]=ch;
for(int i=2;i<=len;i++){s[i]=getchar();}
s[len+1]='\0';
}

int main(){
freopen("1269.in","r",stdin);
freopen("1269.out","w",stdout);
scanf("%d",&n);
Build_First();
for(int i=1;i<=n;i++){
	char opt[10];
	scanf("%s",opt);
	if(opt[0]=='M'){
		int k;
		scanf("%d",&k);
		move_to=k;
	}
	if(opt[0]=='I'){
		int tot;
		scanf("%d",&tot);
		GetString(tot);
		Insert(move_to,tot);
	}
	if(opt[0]=='D'){
		int tot;
		scanf("%d",&tot);
        Delete(move_to+1,tot);
	}
	if(opt[0]=='R'){
		int tot;
		scanf("%d",&tot);
		Reverse(move_to+1,tot);
	}
	if(opt[0]=='G'){
        printf("%c\n",GetKey(move_to+1));
	}
	if(opt[0]=='P')move_to--;
	if(opt[0]=='N')move_to++;
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 666

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com