「PA 2020」Tekstówka 题解

算法思路

本题使用分治算法结合动态规划预处理来解决多组区间最长公共子序列查询问题。核心思想是通过分治将大问题分解为子问题，并利用预处理信息快速合并答案。

关键观察

1. 分治策略

将字符串 $s$ 的区间 $[l, r]$ 分成两半：

• 左半部分 $[l, mid]$
• 右半部分 $[mid+1, r]$

2. 信息合并

对于跨越中间点的查询，答案可以分解为：

$$LCS(s_{a,b}, t_{c,d}) = \max_{c \leq k \leq d+1} \left[LCS(s_{a,mid}, t_{c,k-1}) + LCS(s_{mid+1,b}, t_{k,d})\right] $$

代码解析

预处理结构体

struct ALCS {
    vector<V> f;
    inline void init(string &s, string &t) {
        int n = s.size(), m = t.size();
        f.resize(n + 1);
        // 动态规划预处理LCS信息
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == t[j - 1]) {
                    f[i][j] = g[i][j - 1];
                    g[i][j] = f[i - 1][j];
                } else {
                    f[i][j] = max(f[i - 1][j], g[i][j - 1]);
                    g[i][j] = min(g[i][j - 1], f[i - 1][j]);
                }
            }
    }
    
    inline V ask(int o, int l, int r) {
        // 查询预处理信息
        V ret(len + 1, 0);
        for (int i = 1; i <= len; i++) {
            // 计算LCS值
            if (j >= f[o + 1][j + 1]) {
                ret[i]++;
                // 更新差分数组
            }
        }
        return ret;
    }
};

分治主函数

void solve(int l, int r, vector<array<int, 5>> &qrs) {
    if (l == r) {
        // 基础情况：单字符
        for (auto [a, b, c, d, id] : qrs)
            for (int j = c; j <= d; j++)
                if (s[a] == t[j])
                    ans[id] = 1;
        return;
    }
    
    int mid = (l + r) >> 1;
    ALCS L, R;
    
    // 预处理左右两部分
    for (int i = mid + 1; i <= r; i++) rs += s[i];
    R.init(rs, t);
    
    for (int i = mid; i >= l; i--) ls += s[i];
    L.init(ls, rt);  // rt是t的逆序
    
    // 分割查询
    vector<array<int, 5>> ql, qr;
    for (auto [a, b, c, d, id] : qrs) {
        if (b <= mid) ql.push_back({a, b, c, d, id});
        else if (a > mid) qr.push_back({a, b, c, d, id});
        else {
            // 跨越中间的查询
            auto fr = R.ask(b - (mid + 1), c, d);
            auto fl = L.ask(mid - a, m - 1 - d, m - 1 - c);
            
            for (int i = c; i <= d + 1; i++)
                ans[id] = max(ans[id], fr[d - i + 1] + fl[i - c]);
        }
    }
    
    solve(l, mid, ql);
    solve(mid + 1, r, qr);
}

算法正确性

分治合并原理

对于跨越 $mid$ 的区间 $s_{a,b}$，可以分解为：

• $s_{a,mid}$ 与 $t_{c,k-1}$ 的 LCS
• $s_{mid+1,b}$ 与 $t_{k,d}$ 的 LCS

通过枚举分割点 $k$，找到最优的合并方案。

逆序字符串处理

左半部分使用逆序的 $t$ 进行预处理，是为了统一处理方向，便于合并计算。

复杂度分析

• 预处理：$O(nm)$ 对于每个分治层
• 查询处理：$O(q \log n \cdot m)$
• 总复杂度：$O(nm \log n + qm \log n)$

关键技巧

1. 分治策略：将区间查询分解为子问题
2. 动态规划预处理：预先计算LCS相关信息
3. 逆序处理：统一左右部分的计算方向
4. 差分数组：高效计算区间LCS值