程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj 1269 文本編輯器editor splay

bzoj 1269 文本編輯器editor splay

編輯：關於C++

題意：中問題。

思路：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);
            }
            else if(cmd[0] == 'R'){
                scanf("%d",&x);
                spt.ROTATE(x);
            }
            else if(cmd[0] == 'G'){
                spt.rotateto(pos+1,null);
                printf("%c\n",root->val);
            }
            /*printf("----------cmd=%d-------------\n",++kase);
            printf("pos=%d sz=%d\n",pos,root->sz);
            printf("%c\n",L(R(root))->val);
            spt.print(root);
            printf("-------------------------------------\n");*/
        }
    }
	return 0;
}