ICPC2017 Asia Regional Tsukuba E Black or White

Dむずくて通せてないですごめんなさい。

問題

n個のセルが黒または白で塗られている。
セルの初期状態およびゴールの状態が与えられる。
セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。
最小で何回の操作で全てのセルをゴールの状態にできるか求めよ。

制約条件

n, k≦50万

解法

塗る区間Aは別の塗る区間Bに完全を内包する（orされる）か、全く交わらないかのどちらかであるとしてよい。何故ならAとBが交わるとき、交わった部分を短くして、A, Bを交わらないような塗り方に変えることができるため。

すると、i番目のセルまでゴールと同じ色にするコストの最小値をdp[i]とすれば、
（jまでが塗ってあり、j+1からiをまず1ストロークで一色に塗ってから、その内部を塗ると考えてよくて、）
dp[i] = min_i-k≦j {dp[j] + cost(j+1, i)}のように書ける。
ここでcost(j, i)はj番目からi番目のセルまでを塗るコストである。

ここで、jはi-k以上であったから、全ての区間は一回で塗ることができて、中に何色の色があるかだけでcost(j, i)が決まる。
色の個数をcとすればc/2+1回で塗ることができる。

iがゴール側で新しい色になっていたとき、（t[i] != t[i - 1]のとき）
i以下の色の種類は全て1が足される。cは切り捨てられるのでそのままだと扱いにくくて、
dp[j] + c(j+1, i) / 2 + 1を
(2*dp[j] + c(j+1, i)) / 2 + 1のように変形し、区間加算のできるRMQに2*dp[j] + (右から見たときの色の個数)をもっておくようにすれば操作がうまくいく。

ソースコード

template<class T>struct SegTree{
	T *dat, *lazy;
	int n;
	SegTree(int size = 1000000){
		for(n = 1; n < size; n *= 2);
		dat = new T[2 * n - 1];
		lazy= new T[2 * n - 1];
		init();
	}
	~SegTree(){ delete [] dat; delete [] lazy; }
	
	void init(){
		rep(i, 2 * n - 1) dat[i] = 0;
		rep(i, 2 * n - 1) lazy[i]= 0;
	}
	void add(int a, int b, ll v, int k, int l, int r){
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){ lazy[k] += v; return; }
		if(lazy[k]){
			lazy[k * 2 + 1] += lazy[k];
			lazy[k * 2 + 2] += lazy[k]; lazy[k] = 0;
		}
		add(a, b, v, k * 2 + 1, l, (l + r) / 2);
		add(a, b, v, k * 2 + 2, (l + r) / 2, r);
		dat[k] = min(dat[k * 2 + 1] + lazy[k * 2 + 1], dat[k * 2 + 2] + lazy[k * 2 + 2]);
	}
	T query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return inf;
		if(a <= l && r <= b) return dat[k] + lazy[k];
		if(lazy[k]){
			lazy[k * 2 + 1] += lazy[k];
			lazy[k * 2 + 2] += lazy[k]; lazy[k] = 0;
		}
		T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	T query(int a, int b){ return query(a, b, 0, 0, n); }
	void add(int a, int b, ll v){ add(a, b, v, 0, 0, n); }
};
int main(){
	int n, len; cin >> n >> len;
	string s, t; cin >> s >> t;
	
	vi ans(n + 1);
	SegTree<int> seg(n + 2);
	rep(i, n){
		int best = inf;
		if(s[i] == t[i]) best = ans[i];
		if(i && t[i - 1] != t[i]) seg.add(0, i, 1);
		best = min(best, (seg.query(max(0, i + 1 - len), i + 1) + 1) / 2 + 1);
		
		seg.add(i + 1, i + 2, 2 * best);
		ans[i + 1] = best;
	}
	cout << ans[n] << endl;
	return 0;
}