P5513 [CEOI2013] Board 题解

P5513

容易发现，每次等价于对一个二进制数进行操作。但是这个二进制数长为 \(n\)，即需要高精。但是这样支持加一和减一是复杂度会退化为 \(\mathcal{O}(n^2)\)，有一个很正常的做法就压位，仿照 bitset 的做法进行操作，复杂度 \(\mathcal{O}(\frac{n ^ 2}{w})\)。

这样已经可以通过了，但发现乘除法就是单点赋值，加减法只需要找到最长的一段后缀 \(0/1\) 的位置并覆盖，可以使用线段树维护。找最长后缀串可以直接线段树上二分。时间复杂度线性对数。

如果觉得线段树上二分写起来有点麻烦的话可以直接在外面套一个二分，复杂度多出一只 \(\log\)。

最后统计答案是简单的，一定是到某一层后横向移动在到另一个点，枚举这个层即可。

代码（\(\mathcal{O}(n\log^2n)\)）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector < int >
#define eb emplace_back
#define pii pair < int, int >
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
int Mbe;
mt19937_64 rng(35);
constexpr int N = 1e5 + 10, inf = 1e9;
int n, m, na, nb;
string a, b;
int val[N << 2], laz[N << 2];
void tag(int x, int v, int L, int R) {
	laz[x] = v;
	val[x] = (R - L + 1) * v;
}
void down(int x, int L, int R) {
	if(~laz[x]) {
		int m = (L + R) >> 1;
		tag(x << 1, laz[x], L, m);
		tag(x << 1 | 1, laz[x], m + 1, R);
		laz[x] = -1;
	}
}
void modify(int x, int L, int R, int l, int r, int v) {
	if(l <= L && R <= r) {
		tag(x, v, L, R);
		return;
	}
	down(x, L, R);
	int m = (L + R) >> 1;
	if(l <= m) modify(x << 1, L, m, l, r, v);
	if(r > m) modify(x << 1 | 1, m + 1, R, l, r, v);
	val[x] = val[x << 1] + val[x << 1 | 1];
}
int ask(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) return val[x];
	down(x, L, R);
	int m = (L + R) >> 1, res = 0;
	if(l <= m) res += ask(x << 1, L, m, l, r);
	if(r > m) res += ask(x << 1 | 1, m + 1, R, l, r);
	return res;
}
void query(int x, int L, int R, int type) {
	if(L == R) {
		if(type == 1) a[L] = val[x] + '0';
		else b[L] = val[x] + '0';
		return;
	}
	down(x, L, R);
	int m = (L + R) >> 1;
	query(x << 1, L, m, type);
	query(x << 1 | 1, m + 1, R, type);
}
int search(int R, int len, int type) {
	int l = 1, r = R;
	while(l <= r) {
		int m = (l + r) >> 1;
		if(ask(1, 1, len, m, R) == (R - m + 1) * type) r = m - 1;
		else l = m + 1;
	}
	return l;
}
void solve(int n, int type) {
	int now = 0;
	memset(laz, -1, sizeof(laz));
	memset(val, 0, sizeof(val));
	string s;
	if(type == 1) s = a;
	else s = b;
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '1') {
			++now;
			modify(1, 1, n, now, now, 1);
		} else if(s[i] == '2') {
			++now;
			modify(1, 1, n, now, now, 2);
		} else if(s[i] == 'U') {
			modify(1, 1, n, now, now, 0);
			--now;
		} else if(s[i] == 'L') {
			int p = search(now, n, 1);
			if(p <= now) modify(1, 1, n, p, now, 2);
			modify(1, 1, n, p - 1, p - 1, 1);
		} else {
			int p = search(now, n, 2);
			if(p <= now) modify(1, 1, n, p, now, 1);
			modify(1, 1, n, p - 1, p - 1, 2);
		}
	}
	query(1, 1, n, type);
	if(type == 1) na = now;
	else nb = now;
}
int Med;
int main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> a >> b;
	n = a.size(), m = b.size();
	a = " " + a, b = " " + b;
	solve(n, 1);
	solve(m, 2);
	if(a > b) {
		swap(na, nb);
		swap(a, b);
	}
	int now = 0, ans = na + nb;
	for(int i = 1; i <= na; ++i) {
		if(now < inf) {
			now *= 2;
			if(a[i] == '1' && b[i] == '2') ++now;
			else if(a[i] == '2' && b[i] == '1') --now;
		}
		ans = min(ans, na - i + nb - i + now);
	}
	cout << ans << "\n";
	cerr << TIME << "ms\n";
	return 0;
}