洛谷 - P4008 - 文本编辑器

https://www.luogu.org/problem/P4008

无旋Treap也可以维护序列。

千万要注意要先判断p节点存在才进行Show操作，不然输出一个'\0'（或者RecBin里面的东西）草。

假如有限制同时存在的节点数量的话，UnBuild操作是显得重要的。

当然这里最主要的是类似笛卡尔树的O(n)建立Treap树。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ls(p) ch[p][0]

#define rs(p) ch[p][1]

const int MAXN = 2000000 + 5;

char val[MAXN];

int ch[MAXN][2], rnd[MAXN], siz[MAXN], tot, root;

int cur;

stack<int> RecBin;

inline void Init() {

    root = 0, tot = 0;

    cur = 0;

    srand(19260817);

    while(RecBin.size())

        RecBin.pop();

}

inline void PushUp(int p) {

    siz[p] = siz[ls(p)] + siz[rs(p)] + 1;

}

void SplitRank(int p, int rk, int &x, int &y) {

    if(!p) {

        x = y = 0;

        return;

    }

    //PushDown(p);

    if(rk <= siz[ls(p)]) {

        y = p;

        SplitRank(ls(p), rk, x, ls(p));

        PushUp(y);

    } else {

        x = p;

        SplitRank(rs(p), rk - siz[ls(p)] - 1, rs(p), y);

        PushUp(x);

    }

}

int Merge(int x, int y) {

    if(!x || !y)

        return x | y;

    //这个是小根Treap

    if(rnd[x] < rnd[y]) {

        //PushDown(x);

        rs(x) = Merge(rs(x), y);

        PushUp(x);

        return x;

    } else {

        //PushDown(y);

        ls(y) = Merge(x, ls(y));

        PushUp(y);

        return y;

    }

}

inline int NewNode(char v) {

    int p;

    if(RecBin.size()) {

        p = RecBin.top();

        RecBin.pop();

    } else

        p = ++tot;

    ch[p][0] = ch[p][1] = 0;

    val[p] = v;

    rnd[p] = rand();

    siz[p] = 1;

    return p;

}

void Show(int p) {

    if(!p)

        return;

    Show(ls(p));

    putchar(val[p]);

    Show(rs(p));

}

//O(n)建树，返回新树的根

int st[MAXN], stop;

char buf[MAXN];

inline int Build(int n) {

    stop = 0;

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

        int tmp = NewNode(buf[i]), last = 0;

        while(stop && rnd[st[stop]] > rnd[tmp]) {

            last = st[stop];

            PushUp(last);

            st[stop--] = 0;

        }

        if(stop)

            rs(st[stop]) = tmp;

        ls(tmp) = last;

        st[++stop] = tmp;

    }

    while(stop)

        PushUp(st[stop--]);

    return st[1];

}

//O(n)回收整棵树

inline void UnBuild(int p) {

    if(!p)

        return;

    UnBuild(ls(p));

    UnBuild(rs(p));

    RecBin.push(p);

}

inline void Move() {

    scanf("%d", &cur);

}

inline void Insert(int &root) {

    int x = 0, y = 0, z = 0, n;

    SplitRank(root, cur, x, z);

    scanf("%d", &n);

    buf[n] = '\0';

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

        char ch = getchar();

        while(ch < 32 || ch > 126 || ch == '\r' || ch == '\n')

            ch = getchar();

        buf[i] = ch;

    }

    y = Build(n);

    root = Merge(Merge(x, y), z);

}

inline void Delete(int &root) {

    int x = 0, y = 0, z = 0, n;

    SplitRank(root, cur, x, y);

    scanf("%d", &n);

    SplitRank(y, n, y, z);

    //会不会太慢了

    UnBuild(y);

    //y=Merge(ls(y),rs(y));

    root = Merge(x, z);

}

inline void Get(int &root) {

    int x = 0, y = 0, z = 0, n = 0;

    SplitRank(root, cur, x, y);

    scanf("%d", &n);

    SplitRank(y, n, y, z);

    Show(y);

    puts("");

    root = Merge(Merge(x, y), z);

}

inline void Prev() {

    --cur;

}

inline void Next() {

    ++cur;

}

char op[20];

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int t;

    scanf("%d", &t);

    Init();

    while(t--) {

        scanf("%s ", op);

        switch(op[0]) {

            case 'M':

                Move();

                break;

            case 'I':

                Insert(root);

                break;

            case 'D':

                Delete(root);

                break;

            case 'G':

                Get(root);

                break;

            case 'P':

                Prev();

                break;

            case 'N':

                Next();

                break;

        }

    }

    return 0;

}

巴特西

洛谷 - P4008 - 文本编辑器 - 无旋Treap

最新文章

热门文章