专栏文章

题解：P11459 [USACO24DEC] It's Mooin' Time P

ケケロシブルアカ
P11459题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqnlq1w
此快照首次捕获于
2025/12/04 07:44
3 个月前
此快照最后确认于
2025/12/04 07:44
3 个月前
查看原文
还是我，我又来介绍复杂度与 LL 无关的算法了（喜提最劣解）。
首先是朴素的 dp，设 fi,jf_{i,j} 为在字符串前 ii 位中，选了 jj 个哞叫子串的最小代价，那么转移很明显：
w(l,r)=[sl=O]al+∑i=l+1r[si=M]aiw(l,r)=[s_l=\mathrm{O} ]a_l+\sum_{i=l+1}^{r}[s_i=\mathrm{M} ]a_i fi,j=min⁡(fi−1,j,fi−L,j−1+w(i−L+1,i))f_{i,j}=\min(f_{i-1,j},f_{i-L,j-1}+w(i-L+1,i))
然后不难发现每个 fif_i 都是凸的，所以考虑使用 Slope Trick 维护这个。
套路的，设 fif_i 的差分数组 gig_i，那么 gi,j=fi,j−fi,j−1g_{i,j}=f_{i,j}-f_{i,j-1}。然后用 gig_i 反代 fif_i，即 fi,j=∑k=1jgi,kf_{i,j}=\sum_{k=1}^{j}g_{i,k}，然后代入 dp 式子，然后就能写出关于 gi,jg_{i,j} 的转移式：
gi,j=fi,j−fi,j−1=min⁡(fi−1,j,fi−L,j−1+w(i−L+1,i))−min⁡(fi−1,j1,fi−L,j−2+w(i−L+1,i))=min⁡(∑k=1jgi−1,k,∑k=1j−1gi−L,k+w(i−L+1,i))−min⁡(∑k=1j−1gi−1,k,∑k=1j−2gi−L,k+w(i−L+1,i))\begin{aligned} g_{i,j}&=f_{i,j}-f_{i,j-1}\\ &=\min(f_{i-1,j},f_{i-L,j-1}+w(i-L+1,i))\\ &-\min(f_{i-1,j_1},f_{i-L,j-2}+w(i-L+1,i))\\ &=\min(\sum_{k=1}^{j}g_{i-1,k},\sum_{k=1}^{j-1}g_{i-L,k}+w(i-L+1,i))\\ &-\min(\sum_{k=1}^{j-1}g_{i-1,k},\sum_{k=1}^{j-2}g_{i-L,k}+w(i-L+1,i))\\ \end{aligned}
左右两个 min⁡\min 差不多，所以直接观察 ∑k=1jgi−1,k\sum_{k=1}^{j}g_{i-1,k} 与 ∑k=1j−1gi−L,k+w(i−L+1,i))\sum_{k=1}^{j-1}g_{i-L,k}+w(i-L+1,i)) 的关系。
我们发现一个东西，就是对于上面的式子，存在一个分割点 pp，满足 j≤pj \le p 的 min⁡\min 取到前者，j>pj>p 的取到后者。
这个比较难证明，大概的理解就是左边的式子 fi−1f_{i-1} 相较右边 fi−Lf_{i-L} 右移了一位，导致了这个 fi−1f_{i-1} 的变化更大，也就是更凸，到了分割点后就一直比 fi−Lf_{i-L} 小了。
知道了存在分割点 pp 后，不难发现上面关于 gi,jg_{i,j} 的转移可以按照 pp 进行分类：
gi,j={gi−1,jj≤p∑k=1j−1gi−L,k+w(i−L+1,i)−∑k=1j−1gi−1,kj=p+1gi−L,j−1j>p+1g_{i,j}= \left\{\begin{matrix} g_{i-1,j} & j \le p\\ \sum_{k=1}^{j-1} g_{i-L,k}+w(i-L+1,i)-\sum_{k=1}^{j-1} g_{i-1,k} & j=p+1\\ g_{i-L,j-1} & j > p + 1 \end{matrix}\right.
接下来讲讲实现。
对于这个 gi,jg_{i,j} 的转移，一段是从 gi−1g_{i-1} 拉过来，还有一段从 gi−Lg_{i-L} 拉过来，所以需要持久化平衡树维护。
对于找分割点 pp，需要先二分这个 pp，然后去平衡树上查询一遍，这一部分是瓶颈，是 O(log⁡2n)O(\log^2 n) 的。
本人使用了 Leafy Tree 进行实现，还需注意这题的空间很小，需要定期把无用的点删掉。
时间复杂度 O(nlog⁡2n)O(n \log^2 n)，与 LL 无关。
平衡树常数很大，跑很慢。
CPP
const int N = 3e5 + 5;
const int M = 1e7 + 5;
const ll LNF = 1e18;
int n, k, m; 
string t;
ll a[N], s[N];
int rub[M], tp, lim;
int rt[N], tot, ls[M], rs[M], sz[M]; ll F[M];
bool vis[M];
int add() {
	lim ++;
	if(tp) return rub[tp --];
	return ++ tot;
}
int add(ll x) {
	int u = add();
	ls[u] = rs[u] = 0;
	sz[u] = 1;
	F[u] = x;
	return u;
}
void up(int u) {
	sz[u] = sz[ls[u]] + sz[rs[u]];
	F[u] = F[ls[u]] + F[rs[u]];
}
int up(int l, int r) {
	int u = add();
	ls[u] = l, rs[u] = r;
	up(u);
	return u;
}
int merge(int u, int v) {
	if(! u || ! v) return u | v;
	if(sz[u] <= sz[v] * 4 && sz[v] <= sz[u] * 4) {
		return up(u, v);
	}
	if(sz[u] >= sz[v]) {
		int l = ls[u], r = rs[u];
		if(sz[l] * 4 > (sz[u] + sz[v])) return merge(l, merge(r, v));
		return merge(merge(l, ls[r]), merge(rs[r], v));
	}
	else {
		int l = ls[v], r = rs[v];
		if(sz[r] * 4 > (sz[u] + sz[v])) return merge(merge(u, l), r);
		return merge(merge(u, ls[l]), merge(rs[l], r));
	}
}
void split(int u, int p, int & x, int & y) {
	if(! u || ! p) {
		x = 0, y = u;
		return;
	}
	if(sz[u] == p) {
		x = u, y = 0;
		return;
	}
	if(p <= sz[ls[u]]) {
		split(ls[u], p, x, y);
		y = merge(y, rs[u]);
	}
	else {
		split(rs[u], p - sz[ls[u]], x, y);
		x = merge(ls[u], x);
	}
}
ll query(int u, int r) {
	if(! u || ! r) return 0;
	if(sz[u] <= r) {
		return F[u];
	}
	if(r <= sz[ls[u]]) return query(ls[u], r);
	return F[ls[u]] + query(rs[u], r - sz[ls[u]]);
}
ll ans[N]; int cnt;
void print(int u) {
	if(! ls[u]) {
		ans[++ cnt] = F[u];
		return;
	}
	print(ls[u]);
	print(rs[u]);
}
void dfs(int u) {
	vis[u] = 1;
	if(! ls[u]) {
		return;
	}
	dfs(ls[u]);
	dfs(rs[u]);
}
void recycle(int l, int r) {
	FOR(i, 1, tot) vis[i] = 0;
	FOR(i, l, r) dfs(rt[i]);
	FOR(i, 1, tot) if(sz[i] && ! vis[i]) {
		sz[i] = 0; 
		rub[++ tp] = i;
		lim --;
	}
}
void solve() {
	cin >> k >> n; m = n / k;
	cin >> t; t = ' ' + t;
	FOR(i, 1, n) cin >> a[i];
	FOR(i, 1, n) s[i] = s[i - 1] + (t[i] == 'O' ? 0 : a[i]);
	REP(i, k) rt[i] = add(LNF);
	FOR(i, k, n) {
		if(lim > M - 200) recycle(i - k, i - 1);
		int L = 1, R = i / k, pos = 0;
		ll cost = s[i] - s[i - k + 1] + (t[i - k + 1] == 'M' ? 0 : a[i - k + 1]);
		while(L <= R) {
			int mid = L + R >> 1;
			ll vl = query(rt[i - 1], mid);
			ll vr = query(rt[i - k], mid - 1) + cost;
			if(vl <= vr) {
				pos = mid;
				L = mid + 1;
			}
			else {
				R = mid - 1;
			}
		}
		ll vl = query(rt[i - 1], pos + 1);
		ll vr = query(rt[i - k], pos) + cost;
		if(pos == i / k) {
			rt[i] = rt[i - 1];
		}
		else if(! pos && vl > vr) {
			rt[i] = merge(add(cost), rt[i - k]);
		}
		else {
			int x, y, z;
			split(rt[i - 1], pos, x, z);
			split(rt[i - k], pos, z, y);
			ll val = query(rt[i - k], pos) - query(rt[i - 1], pos) + cost;
			rt[i] = merge(merge(x, add(val)), y);
		}
	}
	print(rt[n]);
	FOR(i, 1, n / k) ans[i] += ans[i - 1];
	FOR(i, 1, n / k) cout << ans[i] << endl;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...