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

题目：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;

}