copy and paste (JOI)

今さら感ありすぎてオワコンな上に赤黒実装ではないため生ゴミ。

実装は RBST(≠Treap) + 永続化 + メモリやばげなら再構築とかいう多分模範解答に近い。

思ったこと

  • RBSTはmerge/splitベースの実装じゃないとよろしくない。
  • newより連続した配列確保したほうがうれしいというのはまあ。
  • 平衡二分木じゃなくても良いから永続化はやんねえかな～
  • 最初の文字列挿入から永続しているとなんか普通に死ぬので、各関数の第三引数に永続化しますフラグを作った。

参考にしたもの

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
 
 
struct T{
        T *l,*r;
        char v;
        int c;
        T(char v) : v(v) , c(1) { l = r = NULL; }
        T(T *a){
                l = a->l;
                r = a->r;
                v = a->v;
                c = a->c;
        }
        T(){}
};
 
#define STQN_SIZE (20000000)
T pool[STQN_SIZE+1000];
int stack_size;
 
T *my_new(char v){ return &(pool[stack_size++] = T(v)); }
T *my_new(T *a){ return &(pool[stack_size++] = T(a)); }
 
int count(T *c){
        if( !c ) return 0;
        else return c->c;
}
T *update(T *c){
        if( !c ) return c;
        c->c = count(c->l) + count(c->r) + 1;
        return c;
}
 
T *merge(T *a,T *b,int flag=1){
        if(!a) return b;
        if(!b) return a;
        if( rand() % ( count(a) + count(b) ) < count(a) ){
                T *R = flag ? my_new(a) : a;
                R->r = merge(a->r,b,flag);
                return update(R);
        }else{
                T *R = flag ? my_new(b) : b;
                R->l = merge(a,b->l,flag);
                return update(R);
        }
}
pair<T*,T*> split(T *c,int k,int flag=1){
        if(!c) return make_pair(c,c);
        
        T *R = flag ? my_new(c) : c;
        if(k <= count(c->l)){
                pair<T*,T*> s = split(c->l,k,flag);
                R->l = s.second;
                return make_pair(s.first,update(R));
        }else{
                pair<T*,T*> s = split(c->r,k - count(c->l) - 1,flag);
                R->r = s.first;
                return make_pair(update(R),s.second);
        }
}
T* insert(T *c,int k,int value){
        pair<T*,T*> div = split(c,k,0);
        T *mono_tree = my_new(value);
        return merge(merge(div.first,mono_tree,0),div.second,0);
}
 
int M,m;
char tmp[1000001];
 
T* generate_tree(){
        stack_size = 0;
        T* root = NULL;
        for(int i = 0 ; tmp[i] ; i++) root = insert(root,i,tmp[i]);
        return root;
}
 
void write(T *c){
        if(m >= M) return;
        if(!c) return;
        write(c->l);
        if( m < M ) tmp[m++] = c->v;
        write(c->r);
}
 
int main(){
        scanf("%d",&M);
        scanf("%s",tmp);
        T *root = generate_tree();
        int N;
        scanf("%d",&N);
        for(int i = 0 ; i < N ; i++){
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                T *substr = split(root,a).second;
                substr = split(substr,b-a).first;
                pair<T*,T*> div = split(root,c);
                root = merge(merge(div.first,substr),div.second);
                if( count(root) >= M ) root = split(root,M).first;
                if( stack_size > STQN_SIZE ){
                        m = 0;
                        write(root);
                        tmp[m] = 0;
                        root = generate_tree();
                }
        }
        m = 0;
        write(root);
        tmp[m] = 0;
        printf("%s\n",tmp);
}