自动搬运

查看原文

来自洛谷，原作者为

	ケロシ Blue Archive

搬运于2025-08-24 23:07:30，当前版本为作者最后更新于2024-12-26 16:15:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

还是我，我又来介绍复杂度与 $L$ 无关的算法了（喜提最劣解）。

首先是朴素的 dp，设 $f_{i,j}$ 为在字符串前 $i$ 位中，选了 $j$ 个哞叫子串的最小代价，那么转移很明显：

$$w(l,r)=[s_l=\mathrm{O} ]a_l+\sum_{i=l+1}^{r}[s_i=\mathrm{M} ]a_i $$$$f_{i,j}=\min(f_{i-1,j},f_{i-L,j-1}+w(i-L+1,i))$$

然后不难发现每个 $f_i$ 都是凸的，所以考虑使用 Slope Trick 维护这个。

套路的，设 $f_i$ 的差分数组 $g_i$，那么 $g_{i,j}=f_{i,j}-f_{i,j-1}$。然后用 $g_i$ 反代 $f_i$，即 $f_{i,j}=\sum_{k=1}^{j}g_{i,k}$，然后代入 dp 式子，然后就能写出关于 $g_{i,j}$ 的转移式：

$$\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$ 差不多，所以直接观察 $\sum_{k=1}^{j}g_{i-1,k}$ 与 $\sum_{k=1}^{j-1}g_{i-L,k}+w(i-L+1,i))$ 的关系。

我们发现一个东西，就是对于上面的式子，存在一个分割点 $p$，满足 $j \le p$ 的 $\min$ 取到前者，$j>p$ 的取到后者。

这个比较难证明，大概的理解就是左边的式子 $f_{i-1}$ 相较右边 $f_{i-L}$ 右移了一位，导致了这个 $f_{i-1}$ 的变化更大，也就是更凸，到了分割点后就一直比 $f_{i-L}$ 小了。

知道了存在分割点 $p$ 后，不难发现上面关于 $g_{i,j}$ 的转移可以按照 $p$ 进行分类：

$$g_{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. $$

接下来讲讲实现。

对于这个 $g_{i,j}$ 的转移，一段是从 $g_{i-1}$ 拉过来，还有一段从 $g_{i-L}$ 拉过来，所以需要持久化平衡树维护。

对于找分割点 $p$，需要先二分这个 $p$，然后去平衡树上查询一遍，这一部分是瓶颈，是 $O(\log^2 n)$ 的。

本人使用了 Leafy Tree 进行实现，还需注意这题的空间很小，需要定期把无用的点删掉。

时间复杂度 $O(n \log^2 n)$，与 $L$ 无关。

平衡树常数很大，跑很慢。

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;
}