hogloidのブログ

へなちょこ

2012合宿Day4 Copy and Paste

みんな大好き永続赤黒木!!!!!!
書いてみると、むちゃくちゃなほど実装重いというわけではないです。重いですが。
正直言って書くより何故赤黒木がうまくいくのかを理解したほうがいいとおもう(今更)

赤黒木の実装の本質は、hosさんのスライドの解説とほぼ同じです
http://hos.ac/slides/20120323_joi_copypaste.pdf

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
static const int BLACK=1,RED=2;
typedef long long int lint;
typedef long double ld;
typedef pair<int,int> pi;
struct node{
	node *l,*r;
	int col,size,rank;
	char val;
	node(){}
	node(node *sl,node *sr,int second){
		l=sl;r=sr;col=second;
	}
};
char s[1000005];
static const int NODE_SIZE=20000000;
struct RBT{
	node nod[NODE_SIZE];
	int cnt;
	node* root;
	RBT(){
		cnt=0;
		root=NULL;
	}
	int getsize(node* a){
		if(a==NULL) return 0;
		return a->size;
	}
	node* make(node *sl,node* sr,int second,char sv='\0'){
		if(cnt==NODE_SIZE-2){
			printf("hogenull__\n");
			exit(0);
		}
		nod[cnt]=node(sl,sr,second);
		nod[cnt].size=getsize(sl)+getsize(sr);
		if(sv!='\0') ++nod[cnt].size;
		nod[cnt].val=sv;
		int left;
		if(sl!=NULL){
			left=sl->rank+(sl->col==BLACK?1:0);
			nod[cnt].rank=left;
		}else nod[cnt].rank=0;
		return &nod[cnt++];
	}
	node* merge2(node *a,node *b){
		if(a->rank<b->rank){
			node *c=merge2(a,b->l);
			if(b->col==BLACK && c->col==RED && c->l->col==RED){
				if(b->r->col==BLACK)
					return make(c->l,make(c->r,b->r,RED),BLACK);
				else return make(make(c->l,c->r,BLACK),make(b->r->l,b->r->r,BLACK),RED);
			}else return make(c,b->r,b->col);
		}else if(a->rank>b->rank){
			node *c=merge2(a->r,b);
			if(a->col==BLACK && c->col==RED && c->r->col==RED){
				if(a->l->col==BLACK)
					return make(make(a->l,c->l,RED),c->r,BLACK);
				else return make(make(a->l->l,a->l->r,BLACK),make(c->l,c->r,BLACK),RED);
			}else return make(a->l,c,a->col);
		}else return make(a,b,RED);
	}
	node* merge(node *a,node *b){
		if(a==NULL) return b;
		if(b==NULL) return a;
		node *c=merge2(a,b);
		if(c->col==RED) return make(c->l,c->r,BLACK);
		return c;
	}
	pair<node*,node*> split(node *a,int k){
		if(k==0) return make_pair((node*)(NULL),a);
		if(k>=a->size) return make_pair(a,(node*)NULL);
		if(k<a->l->size){
			pair<node*,node*> res=split(a->l,k);
			return make_pair(res.first,merge(res.second,a->r));
		}else if(k>a->l->size){
			pair<node*,node*> res=split(a->r,k-a->l->size);
			return make_pair(merge(a->l,res.first),res.second);
		}else return make_pair(a->l,a->r);
	}
	void print(node* a){
		if(a==NULL) return;
		if(a->val=='\0'){
			print(a->l);print(a->r);
		}else putchar(a->val);
	}
	int cnt2;
	void print2(node* a){
		if(a==NULL) return;
		if(a->val=='\0'){
			print2(a->l);print2(a->r);
		}else s[cnt2++]=a->val;
	}
	node *tmp[1100005],*tmp2[1100005];
	void rebuild(char* s){
		int len=strlen(s);
		cnt=0;
		for(int i=0;i<len;++i) tmp[i]=make(NULL,NULL,BLACK,s[i]);
		if(len==1) tmp2[0]=tmp[0];
		while(len>1){
			for(int i=0;i<(len+1)/2;++i){
				if(i*2+1<len)
					tmp2[i]=merge(tmp[i*2],tmp[i*2+1]);
				else tmp2[i]=tmp[i*2];
			}
			for(int i=0;i<(len+1)/2;++i) tmp[i]=tmp2[i];
			len=(len+1)/2;
		}
		root=tmp2[0];
	}
};
RBT tree;
int m,n;
int main(){
	scanf("%d",&m);
	scanf("%s",s);
	tree.rebuild(s);
	scanf("%d",&n);
	for(int hoge=0;hoge<n;++hoge){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		pair<node*,node*> ins=tree.split(tree.root,a),ins2;
		ins2=tree.split(ins.second,b-a);
		pair<node*,node*> insed=tree.split(tree.root,c);

		tree.root=tree.merge(tree.merge(insed.first,ins2.first),insed.second);
		tree.root=tree.split(tree.root,m).first;
		if(tree.cnt>=19000000){
			tree.cnt2=0;
			tree.print2(tree.root);
			s[tree.cnt2]='\0';
			tree.rebuild(s);
		}
	}
	tree.print(tree.root);
	putchar('\n');
	return 0;
}