// 【模板】文艺平衡树
#include <iostream>
#define lc son[p][0]
#define rc son[p][1]

const int N = 1 << 22;
int n, root, idx, now;
int son[N][2], siz[N], pri[N], tag[N];
char val[N];

void swap(int &x, int &y) {
    int z = x;
    x = y;
    y = z;
}

void up(int p) { siz[p] = siz[lc] + siz[rc] + 1; }

void split(int p, int v, int &l, int &r) {
    if (!p) {
        l = r = 0;
        return;
    }
    if (siz[lc] < v) {
        l = p;
        split(rc, v - siz[lc] - 1, rc, r);
    } else {
        r = p;
        split(lc, v, l, lc);
    }
    up(p);
}

int merge(int l, int r) {
    if (!l || !r) return l + r;
    if (pri[l] > pri[r]) {
        son[l][1] = merge(son[l][1], r);
        up(l);
        return l;
    } else {
        son[r][0] = merge(l, son[r][0]);
        up(r);
        return r;
    }
}

void insert(int v) {
    char ch = getchar();
    int l, r;
    split(root, now, l, r);
    for (int i = 1; i <= v; i++) {
        ch = getchar();
        while (' ' < ch || ch >'z') ch = getchar();
        int p = ++idx;
        pri[p] = rand();
        val[p] = ch;
        siz[p] = 1;
        l = merge(l, p);
    }

    root = merge(l, r);
}

void Delete(int v) {
    int l = 1, r = now, p;
    split(root, now + v, l, r);
    split(l, now, l, p);
    root = merge(l, r);
}

void dfs(int p) {
    if (!p) return;
    dfs(lc);
    printf("%c", val[p]);
    dfs(rc);
}

int main()
{
    scanf("%d", &n);
    while (n--) {
        std::string s;
        std::cin >> s;
        int k;
        if (s == "Insert") {
            scanf("%d", &k);
            insert(k);
        } else if (s == "Delete") {
            scanf("%d", &k);
            Delete(k);
        } else if (s == "Get") {
            scanf("%d", &k);
            dfs(k);
        } else if (s == "Move") {
            scanf("%d", &now);
        } else if (s == "Prev") {
            now--;
        } else if (s == "Next") {
            now++;
        }
    }
    return 0;
}

1 条评论

  • 1