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

· · 题解

还是我，我又来介绍复杂度与 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;
}