某岛

… : "…アッカリ~ン . .. . " .. .
April 5, 2020

UVa 12538 – Version Controlled IDE

Vjudge
挖掘 Treap 的潜力。。

https://vjudge.net/solution/1643343
https://user.qzone.qq.com/251815992/blog/1381870978
https://morris821028.github.io/2014/10/27/oj/uva/uva-12538/

題目有三種字符串的操作:
– 1 p s: 在當前字串位置 p 後插入 s 字串。
– 2 p c: 將當前字串位置 p 後面連續 c 個字符移除。
– 3 v p c: 在版本號 v 的字串中,在位置 p 之後印出 c 個字元。

强制在线。

const int N = int(1e7) + 9, SN = int(1e6) + 9, VN = int(5e4) + 9;

namespace Treap{

    int c[2][N], sz[N], ww[N], tot; char ch[N], str[SN];
    int T[VN], _T, tt;

#define l c[0]
#define r c[1]
#define lx l[x]
#define rx r[x]
#define ml (a + b >> 1)
#define mr (ml + 1)
#define lc a, ml
#define rc mr, b

    inline int update(int x){
        sz[x] = sz[lx] + 1 + sz[rx];
        return x;
    }

    inline int new_node(char chx){
        int x = ++tot;
        lx = rx = 0, ww[x] = rand(), sz[x] = 1, ch[x] = chx;
        return x;
    }

    inline int new_node(int xx){
        int x = ++tot;
        lx = l[xx], rx = r[xx], ww[x] = ww[xx], sz[x] = sz[xx], ch[x] = ch[xx];
        return x;
    }

    int merge(int a, int b){
        if(!a||!b) return a|b;

        if(ww[a] > ww[b]){
            a = new_node(a), r[a] = merge(r[a], b);
            return update(a);
        }
        else{
            b = new_node(b), l[b] = merge(a, l[b]);
            return update(b);
        }
    }

    void split(int x, int p, int &a, int &b){
        if(!p) a = 0, b = x; else if(sz[x] == p) a = x, b = 0;
        else{
            x = new_node(x);
            if(p <= sz[lx]) split(lx, p, a, b), lx = b, b = x;
            else split(rx, p-sz[lx]-1, a, b), rx = a, a = x;
            update(x);
        }
    }

    int build(int a = 0,int b = strlen(str)){
        if (a >= b) return 0;
        int x = new_node(str[ml]);
        lx = build(lc), rx = build(rc);
        update(x);
        return x;
    }

    void print(int x,int a,int b){
        if (!x) return;
        if (a <= sz[lx]) print(lx, a, b); a -= sz[lx]+1, b -= sz[lx]+1;
        if (a <= 0 && 0 < b) putchar(ch[x]), _T += ch[x] == 'c';
        if (1 < b) print(rx, a, b);
    }
} using namespace Treap;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("print.txt", "w", stdprint);
#endif

	int t, s, n, a, b, _; Rush switch(RD()){
        case 1:
            RD(s)-=_T, RS(str);
            split(T[tt], s, a, b);
            T[++tt] = merge(merge(a, build()), b);
            break;
        case 2:
            RD(s, n), s-=_T,n-=_T;
            split(T[tt], s-1, a, b), split(b, n, _, b);
            T[++tt] = merge(a, b);
            break;
        default:
            RD(t, s, n), t-=_T,s-=_T,n-=_T;
            print(T[t], s, s+n), puts("");
    }
}