HSNU Online Judge Problem : 226 - K. CP

HOJ226.cpp

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <new>
using namespace std;

struct Tree;

class TreeRef {
    Tree* t;
public:
    TreeRef(Tree* tt);
    TreeRef(const TreeRef& tt);
    TreeRef(TreeRef&& tt);
    ~TreeRef();
    operator bool () const;
    Tree* operator -> () const;
    TreeRef& operator = (const TreeRef& rhs);
};

struct Tree {
    int refs;
    const char ch;
    const int size;
    const TreeRef lchild, rchild;

    Tree(char c);
    Tree(char c, const TreeRef& l, const TreeRef& r);
};

struct Allocator {
    union UU {
        UU * next;
        Tree t;
        UU() : next(this + 1) {}
        ~UU() {}
    } data[1005000];
    UU * head = data;
    Tree * allocate() {
        UU* h = head;
        head = head->next;
        return &h->t;
    }
    void deallocate(Tree* t) {
        UU* h = reinterpret_cast<UU*>(t);
        h->next = head;
        head = h;
    }
} allocator;

void ref(Tree* t) { if(t) t->refs++; }
void unref(Tree* t) {
    if(t && !--t->refs) {
        t->~Tree();
        allocator.deallocate(t);
    }
}

TreeRef::TreeRef(Tree* tt) : t(tt) { ref(t); }
TreeRef::TreeRef(const TreeRef& tt) : TreeRef(tt.t) {}
TreeRef::TreeRef(TreeRef&& tt) : t(tt.t) { tt.t = nullptr; }
TreeRef::~TreeRef() { unref(t); }
TreeRef::operator bool () const { return t; }
Tree* TreeRef::operator -> () const { return t; }
TreeRef& TreeRef::operator = (const TreeRef& rhs) {
    if(t != rhs.t) {
        unref(t);
        t = rhs.t;
        ref(t);
    }
    return *this;
}

int getsize(const TreeRef& p) { return p ? p->size : 0; }

Tree::Tree(char c) : refs(0), ch(c), size(1), lchild(nullptr), rchild(nullptr) {}
Tree::Tree(char c, const TreeRef& l, const TreeRef& r) : refs(0), ch(c), size(1 + getsize(l) + getsize(r)), lchild(l), rchild(r) {}

TreeRef merge(const TreeRef& lhs, const TreeRef& rhs) {
    if(!lhs) return rhs;
    if(!rhs) return lhs;
    if(rand() % (lhs->size + rhs->size) < lhs->size) {
        return new (allocator.allocate()) Tree(lhs->ch, lhs->lchild, merge(lhs->rchild, rhs));
    } else {
        return new (allocator.allocate()) Tree(rhs->ch, merge(lhs, rhs->lchild), rhs->rchild);
    }
}

TreeRef first(const TreeRef& t, int x) {
    if(x == 0) return nullptr;
    if(x == t->size) return t;
    if(x <= getsize(t->lchild))
        return first(t->lchild, x);
    else
        return new (allocator.allocate()) Tree(t->ch, t->lchild, first(t->rchild, x - getsize(t->lchild) - 1));
}

TreeRef second(const TreeRef& t, int x) {
    if(x == 0) return t;
    if(x == t->size) return nullptr;
    if(x <= getsize(t->lchild))
        return new (allocator.allocate()) Tree(t->ch, second(t->lchild, x), t->rchild);
    else
        return second(t->rchild, x - getsize(t->lchild) - 1);
}

TreeRef build(char * s, int l, int r) {
    if(l == r) return nullptr;
    int m = (l + r) / 2;
    return new (allocator.allocate()) Tree(s[m], build(s, l, m), build(s, m + 1, r));
}

TreeRef copy(const TreeRef& t, int l, int r) {
    return second(first(t, r), l);
}

TreeRef insert(const TreeRef& t, const TreeRef& u, int x) {
    return merge(merge(first(t, x), u), second(t, x));
}

TreeRef crop(const TreeRef& t, int m) {
    return t->size <= m ? t : first(t, m);
}

void print(const TreeRef& t) {
    if(t) {
        print(t->lchild);
        putchar(t->ch);
        print(t->rchild);
    }
}

char s[1000001];

int main(){
    srand(time(nullptr));

    int m, n;
    scanf("%d %s %d", &m, s, &n);

    TreeRef t = build(s, 0, strlen(s));

    for(int i = 0; i < n; i++) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        t = crop(insert(t, copy(t, l, r + 1), x), m);
    }
    print(t);
    putchar('\n');
}