JOI春合宿2012 Day4 「Copy and Paste」

想定解法は「永続平衡二分木」を使うものですが、そんなもの一般人には書けません。そこで、一般人にも使える道具だけを使って点数を取りに行く試みをしました。

解法

バケット法のようなものを使う。
文字列の連続した部分を、「文字列へのポインタ」と「長さ」のペアとして持っておく。ポインタは文字列プールを指し、そこに実際の文字列を持っておく。
文字列のコピー、ペーストは、範囲を切断したりコピーすることによって実現する。
ただし、このままだと範囲が細分化されすぎて、結局文字で持つのと変わらなくなってしまう（逆に定数倍がひどくなる）。
そこで、範囲の列に「隣り合う範囲の長さの和は、閾値 B 以上になるようにする」という制約を課す。この制約を満たしていないときには、内容をコピーして、長い範囲を作り、それに置き換える。これによって、範囲の数が 2N/B 程度に抑えられる。
このアルゴリズムの計算量はよくわからないが、O((N+M)√N)よりは速くならないと考えられる。想定解法のO((N+M) log N) よりははるかに悪いが、実際に動かすとかなり高速に動く。
実際に ATCODER 上で実行したところ、1つのケースを除いて AC であった。(訂正:B=1200としたらすべて AC しました)仮想マシンと ATCODER の定数倍の差はあるものの、本番でも50〜60%程度の得点は得られたと考えられる。

コード

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>

using namespace std;

#define BSIZE (500 * 1024 * 1024)

struct state
{
	char* top;
	int size;

	state(){ }
	state(char* t, int s){ top = t; size = s; }
};

void _pstat(state& s)
{
	printf("%d(", s.size);
	for(int i=0;i<s.size;i++) printf("%c", s.top[i]);
	printf(") ");
}

int N, M, B;
char in[1500001];
char buf[BSIZE]; int bLast;
vector<state> st;

void pstat()
{
	for(int i=0;i<st.size();i++) _pstat(st[i]); puts("");
}

void split(int p)
{
	for(int i=0;i<st.size();i++){
		if(p <= 0) return;
		if(p < st[i].size){
			state st1(st[i].top, p), st2(st[i].top + p, st[i].size - p);
			st[i] = st1;
			st.insert(st.begin() + (i+1), st2);
		}
		p -= st[i].size;
	}
}

void insert(int l, int r, int p)
{
	vector<state> inv;
	int s=0;
	for(int i=0;i<st.size();i++){
		int il=max(l,s), ir=min(r,s+st[i].size);
		if(il<ir){
			inv.push_back(state(st[i].top + (il - s), ir-il));
		}
		s += st[i].size;
		if(s >= r) break;
	}
	for(int i=0;i<=st.size();i++){
		if(p==0){
			st.insert(st.begin() + i, inv.begin(), inv.end());
			break;
		}
		p -= st[i].size;
	}
}

void simplify()
{
	vector<state> tmp;
	int ps=0, sum=0;
	for(;ps<st.size();){
		if(sum >= N) break;
		int ps2=ps, sum2=0;
		while(ps2<st.size() && sum2<B){
			sum2 += st[ps2++].size;
		}

		if(ps2 - ps == 1){
			tmp.push_back(st[ps]);
			ps = ps2;
			sum += sum2;
			continue;
		}

		int bp = bLast;
		for(int i=ps;i<ps2;i++){
			memcpy(buf+bLast, st[i].top, st[i].size);
			bLast += st[i].size;
		}
		tmp.push_back(state(buf+bp, sum2));
		sum += sum2;
		ps = ps2;
	}
	st.swap(tmp);
}

bool danger()
{
	return bLast >= BSIZE - N;
}

void restore()
{
	int ps = 0;
	for(int i=0;i<st.size();i++){
		memcpy(in+ps, st[i].top, st[i].size);
		ps += st[i].size;
	}
	ps = min(ps, N);
	in[ps] = '\0';

	memcpy(buf, in, ps);
	bLast = ps;
	st.push_back(state(buf, ps));
}

int main()
{
	int L, R, P;
	B = 1200;
	scanf("%d%s%d", &N, in, &M);

	int ln = strlen(in);
	memcpy(buf, in, ln);
	bLast = ln;
	st.push_back(state(buf, strlen(in)));

	for(int i=0;i<M;i++){
		scanf("%d%d%d", &L, &R, &P);

		//fprintf(stderr, "%d %d\n", i, bLast);
		split(P);

		//pstat();
		insert(L, R, P);
		//pstat();
		simplify();
		//pstat();

		if(danger()){
			restore();
		}
	}

	restore();
	puts(in);
	return 0;
}