BZOJ-1269: [AHOI2006]文本编辑器editor

作者: acccccc | 来源:发表于2018-10-03 13:34 被阅读3次

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1269

跟NOI03的那道editor没什么区别,只是多维护一个Reverse(翻转)标记,旋转的时候记得下传标记。

代码:

738b4710b912c8fc9c4aabdefe039245d6882163.jpg.png
#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std;

 

#define MAXN 2000010

#define L(t) T[t].Left

#define R(t) T[t].Right

#define S(t) T[t].Size

#define C(t) T[t].Char

#define update(t) S(t)=S(L(t))+S(R(t))+1

#define Cl(r,t) (r<S(L(t)))

#define Ls(t) T[t].Lay

 

struct node {

    int Left,Right,Size,Char;

    bool Lay;

    node () {

        Left=Right=Size=Char=0;

        Lay=false;

    }

} T[MAXN];

 

int n,roof=0,M=0;

int s[MAXN];

 

void pushdown(int t) {

    if (t&&Ls(t)) {

       swap(L(t),R(t));

        Ls(t)^=true,Ls(L(t))^=true,Ls(R(t))^=true;

    }

}

 

void zag(int &t) {

    pushdown(t);pushdown(R(t));

    int k=R(t);

   R(t)=L(k);update(t);

   L(k)=t;update(k);

    t=k;

}

 

void zig(int &t) {

   pushdown(t);pushdown(L(t));

    int k=L(t);

   L(t)=R(k);update(t);

   R(k)=t;update(k);

    t=k;

}

 

bool splay(int r,int &t,bool flag) {

    pushdown(t);

    if (r==S(L(t))) return false;

    bool w=splay(Cl(r,t)?r:r-S(L(t))-1,Cl(r,t)?L(t):R(t),true);

    if (w) {

        if (Cl(r,t)) {

            if (Cl(r,L(t))) zig(t); else zag(L(t));

            zig(t);

        } else {

            if (!Cl(r-S(L(t))-1,R(t))) zag(t); else zig(R(t));

            zag(t);

        }

    } else if (!flag) if (Cl(r,t)) zig(t);else zag(t);

    return w^true;

}

 

void build(int l,int r,int &t) {

    if (l>r) { t=0; return ; }

    int mid=(l+r)>>1;

   C(t=++M)=s[mid];

    S(t)=r-l+1;

    build(l,mid-1,L(t)),build(mid+1,r,R(t));

    update(t);

}

 

void getstring(int N) {

    int ch;

    for (int i=0;i++<N;) {

        for (ch=getchar();ch=='\n';ch=getchar()) ;

        s[i]=ch;

    }

}

 

int main() {

    scanf("%d\n",&n);

   roof=++M;R(roof)=++M;

    C(1)=C(2)=int('$');

    while (n--) {

        char st[20];

        int m,Tr;

        scanf("%s",&st);

        switch (st[0]) {

            case'M':

               scanf("%d",&m);

               splay(m,roof,false);

                break;

            case'I':

                Tr=0;

               scanf("%d",&m);

               getstring(m);

               build(1,m,Tr);

               splay(0,R(roof),false);

               L(R(roof))=Tr;

                update(R(roof));

               update(roof);

                break;

            case'D':

               scanf("%d",&m);

               splay(min(m,S(R(roof))-1),R(roof),false);

               L(R(roof))=0;

               update(R(roof));

                update(roof);

                break;

            case'G':

               pushdown(roof);

               splay(0,R(roof),false);

               printf("%c\n",char(C(R(roof))));

                break;

            case'P':

                splay(S(L(roof))-1,roof,false);

                break;

            case'N':

               splay(S(L(roof))+1,roof,false);

                break;

            case'R':

               scanf("%d",&m);

               splay(m,R(roof),false);

                Ls(L(R(roof)))^=true;

                break;

        }

    }

    return 0;

}


相关文章

  • BZOJ-1269: [AHOI2006]文本编辑器editor

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1269 跟...

  • sed和tr基本用法

    sed:(Stream Editor)流编辑器。它是行编辑器,处理纯ASCII码文本,实现逐行进行处理文本。 se...

  • 富文本编辑器1.0.x

    sy-editor 新氧富文本编辑器 sy-editor 1.0.0 第一版本,基于wangeditor 富文本编...

  • git设置文本编辑器

    设置文本编辑器,命令如下: git config --global core.editor [编辑器名字] 例如...

  • 8-Linux sed 命令用法

    sed的基本用法 sed : String EDitor (流编辑器)行编辑器,逐行处理文本 全屏编辑器(vi) ...

  • Angular使用wysiwyg-editor在开发时期出现需要

    在使用angular开发网站后台需要富文本编辑器,看上了wysiwyg-editor这个富文本编辑器,很漂亮,基本...

  • sed

    文本处理sed sed(Stream EDitor, 行编辑器):处理文本的工具。sed是一种流编辑器,它一次处...

  • inux学习 Day15-sed基本用法

    文本处理工具:grep,sed(流编辑器),awk sed基本用法:sed(Stream EDitor)行编辑器(...

  • sed和tr命令的用法

    sed基本用法:sed:(Stream Editor)流编辑器。它是行编辑器,处理纯ASCII码文本,实现逐行进行...

  • note_11.4_sed命令

    文本处理三剑客: grep, egrep, fgrep:文本过滤器 sed:Stream EDitor,流编辑器,...

网友评论

    本文标题:BZOJ-1269: [AHOI2006]文本编辑器editor

    本文链接:https://www.haomeiwen.com/subject/wfbzoftx.html