BZOJ-1507: [NOI2003]Editor

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

用splay维护序列的方法维护就可以了，然后直接把根节点作为光标方便操作（比NOI05的那道splay好写多了。。。）

代码:

1e30e924b899a901a07541251f950a7b0208f565.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)))
 
struct node {
    int Left,Right,Size,Char;
    node () {
        Left=Right=Size=Char=0;
    }
} T[MAXN];
 
int n,roof=0,M=0;
int s[MAXN];
 
void zag(int &t) {
    int k=R(t);
    R(t)=L(k);update(t);
    L(k)=t;update(k);
    t=k;
}
 
void zig(int &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) {
    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;
    }
}
 
void Print(int t) {
    if (!t) return ;
    Print(L(t));
    printf("%c",char(C(t)));
    Print(R(t));
}
 
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':
                scanf("%d",&m);
                splay(m,R(roof),false);
                Print(L(R(roof)));
                printf("\n");
                break;
            case 'P':
                splay(S(L(roof))-1,roof,false);
                break;
            case 'N':
                splay(S(L(roof))+1,roof,false);
                break;
        }
    }
    return 0;
}