bzoj 1269 文本编辑器editor splay - c++编程基础

TOP

bzoj 1269 文本编辑器editor splay(一)

2015-07-20 17:21:38 来源: 作者: 【大中小】浏览:10次

题意：中问题。

思路：splay的基本操作，注意读入，详见代码：

/*********************************************************
  file name: bzoj1269.cpp
  author : kereo
  create time:  2015年02月01日 星期日 16时57分30秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=1024*1024*2+100; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x->ch[0]) #define R(x) (x->ch[1]) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int m,top,cnt,pos; int st[MAXN]; char str[MAXN]; struct node{ char val; int sz,tag; node *fa,*ch[2]; }nod[MAXN],nil,*root,*null; struct Splay{ void rotate(node *x,int d){ node *y=x->fa; push_down(y); push_down(x); y->ch[d^1]=x->ch[d]; if(x->ch[d]!=null) x->ch[d]->fa=y; x->fa=y->fa; if(y->fa!=null){ int d=y->fa->ch[0] == y ? 0 : 1; y->fa->ch[d]=x; } y->fa=x; x->ch[d]=y; push_up(y); } void splay(node *x,node *fa){ while(x->fa!=fa){ push_down(x); node *y=x->fa; if(y->fa == fa){ int d=y->ch[0] == x ? 1 : 0; rotate(x,d); } else{ int d=y->fa->ch[0] == y ? 1 : 0; if(y->ch[d] == x){ rotate(x,d^1); rotate(x,d); } else{ rotate(y,d); rotate(x,d); } } } push_up(x); if(fa == null) root=x; } void rotateto(int k,node *fa){ node *rt=root; push_down(rt); while(L(rt)->sz!=k){ if(L(rt)->sz>k) rt=L(rt); else{ k-=(L(rt)->sz+1); rt=R(rt); } push_down(rt); } splay(rt,fa); } void Delete(node *rt){ if(rt == null) return ; st[top++]=rt-nod; Delete(L(rt)); Delete(R(rt)); } void print(node *rt){ if(rt == null) return ; push_down(rt); printf("rt->val=%c rt->sz=%d L(rt)->val=%c R(rt)->val=%c rt->fa->val=%c\n",rt->val,rt->sz,L(rt)->val,R(rt)->val,rt->fa->val); print(L(rt)); print(R(rt)); } //---------------------------------------------------// void newnode(node *&x,node *fa,char val){ if(top) x=&nod[st[--top]]; else x=&nod[++cnt]; x->sz=1; x->val=val; x->tag=0; x->fa=fa; L(x)=R(x)=null; } void init(){ cnt=top=pos=0; nil.sz=nil.tag=0;nil.val='*'; null=&nil; root=null; newnode(root,null,'#'); newnode(R(root),root,'!'); push_up(R(root)); push_up(root); } void push_down(node *rt){ if(rt->tag){ L(rt)->tag^=1; R(rt)->tag^=1; swap(L(rt),R(rt)); rt->tag^=1;; } } void push_up(node *rt){ rt->sz=L(rt)->sz+R(rt)->sz+1; } void build(node *&rt,node *fa,int l,int r){ if(l>r) return ; int mid=(l+r)>>1; newnode(rt,fa,str[mid]); build(L(rt),rt,l,mid-1); build(R(rt),rt,mid+1,r); push_up(rt); } void INSERT(){ int len; scanf("%d%*c",&len); //没有%*c会报RE //scanf("%s",str); gets(str); rotateto(pos,null); rotateto(pos+1,root); build(L(R(root)),R(root),0,len-1); push_up(R(root)); push_up(root); } void ROTATE(int n){ rotateto(pos,null); rotateto(pos+n+1,root); L(R(root))->tag^=1; } void DELETE(int n){ rotateto(pos,null); rotateto(pos+n+1,root); Delete(L(R(root))); L(R(root))=null; push_up(R(root)); push_up(root); } }spt; int main(){ //freopen("in.txt","r",stdin); int kase=0; while(~scanf("%d",&m)){ spt.init(); int x; char cmd[N]; while(m--){ scanf("%s",cmd); if(cmd[0] == 'M'){ scanf("%d",&x); pos=x; } else if(cmd[0] == 'P'){ scanf("%d",&x); pos--; } else if(cmd[0] == 'N'){ scanf("%d",&x); pos++; } else if(cmd[0] == 'I'){ spt.INSERT(); } else if(cmd[0] == 'D'){ scanf("%d",&x); spt.DELETE(x

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 3463 Sightseeing	下一篇：Coderforces 509B

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: