思路与算法

令S_i为删除难度前缀。第一种转移dp_j+a(S_i-S_j)²+b，用斜率-2aS_j和截距dp_j+aS_j²的下凸包；S非降，处理同斜率只保留较小截距。第二种转移dp_j-cS_j+cS_i+d，其合法j由两套字符滑窗给出：最大频次≤r的起点下界，以及最大频次≥l的起点上界，用单调队列维护该窗口最小值。

正确性说明

任一删除方案的最后子串唯一确定前缀j。平方展开给出第一组全部候选，凸包按单调条件维护准确。子串起点右移时最大字符频次不增，所以两个频次条件形成交窗口；双滑窗边界精确，队列淘汰过期和永劣前缀后提供第二组最小值。两类取小即最优前缀分割。

复杂度

读入和前缀O(n)，每字符进出两个滑窗一次；字符集26使频次最大值扫描O(26n)，凸包和单调队列O(n)，总O(26n)时间，O(n)空间。

易错点

dif可为0，必须合并重复斜率。l>r时禁用第二方式。不能用某一种字符频次代替子串最大频次；两个窗口边界转成前缀下标时差1。平方及交点乘积使用64位和128位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct L {
    ll m, b;
};
__int128 value(L l, ll x) {
    return (__int128)l.m * x + l.b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, a, b, c, d, l, r;
    cin >> n >> a >> b >> c >> d >> l >> r;
    string s;
    cin >> s;
    vector<ll> S(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        S[i] = S[i - 1] + x;
    }
    deque<L> h;
    deque<int> q;
    h.push_back({0, 0});
    array<int, 26> cl{}, cr{};
    int leftR = 0, leftL = 0, added = -1;
    for (int i = 1; i <= n; i++) {
        cl[s[i - 1] - 'a']++;
        cr[s[i - 1] - 'a']++;
        while (*max_element(cr.begin(), cr.end()) > r)
            cr[s[leftR++] - 'a']--;
        while (*max_element(cl.begin(), cl.end()) >= l)
            cl[s[leftL++] - 'a']--;
        while (h.size() > 1 && value(h[0], S[i]) >= value(h[1], S[i]))
            h.pop_front();
        dp[i] = a * S[i] * S[i] + b + (ll)value(h.front(), S[i]);
        if (l <= r) {
            while (added < leftL - 1) {
                ++added;
                while (!q.empty() && dp[q.back()] - c * S[q.back()] >= dp[added] - c * S[added])
                    q.pop_back();
                q.push_back(added);
            }
            while (!q.empty() && q.front() < leftR)
                q.pop_front();
            if (!q.empty())
                dp[i] = min(dp[i], c * S[i] + d + dp[q.front()] - c * S[q.front()]);
        }
        L z{-2LL * a * S[i], dp[i] + a * S[i] * S[i]};
        if (!h.empty() && h.back().m == z.m) {
            if (h.back().b <= z.b)
                continue;
            h.pop_back();
        }
        while (h.size() > 1) {
            L x = h[h.size() - 2], y = h.back();
            if ((__int128)(y.b - x.b) * (y.m - z.m) >= (__int128)(z.b - y.b) * (x.m - y.m))
                h.pop_back();
            else
                break;
        }
        h.push_back(z);
        cout.flush();
    }
    for (int i = 1; i <= n; i++)
        cout << dp[i] << '\n';
}