25四川省赛

发表于 2026-04-03 更新于 2026-04-11 分类于 ACM ， VP 记录阅读次数：作者 Pomelorin ， Cool-breeze

F. Inversion Pairs

只含有 01? 三种字符的字符串，可以把 ? 变成 0 或 1，求逆序对最多为多少。

逆序对贪心填法一定是左边都填 1，右边都填 0，枚举这个分界点即可。

预处理前缀 1 个数与后缀 0 个数，先假设都填 0，之后从左向右开始填 1。贡献变化为加后面 0 的个数减前面 1 的个数。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void solve()
{
    ll n, ans = 0, cntq = 0, cur = 0;
    string s;
    cin >> n >> s;
    s = " " + s;
    ll pre1[n + 10] = {}, suc0[n + 10] = {}, preq[n + 10] = {};
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '0')
        {
            suc0[i] = 1;
        }
        if (s[i] == '1')
        {
            pre1[i] = 1;
        }
        if (s[i] == '?')
        {
            preq[i] = 1;
            cntq++;
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        pre1[i] += pre1[i - 1];
        preq[i] += preq[i - 1];
    }
    for (ll i = n; i >= 1; i--)
    {
        suc0[i] += suc0[i + 1];
    }
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] != '1')
        {
            cur += pre1[i];
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '?')
        {
            cur += (cntq - preq[i]) + suc0[i];
            cur -= (preq[i] - 1) + pre1[i];
        }
        ans = max(ans, cur);
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

H. Hututu

棋子每次可以走 \((x\pm1\text{or}2,y\pm1\text{or}2)\)，问最少走多少步从 \((x,y)\) 到 \((X,Y)\)。

考虑 x 和 y 轴分开来，每次最多走 2 格，然后结果就是 x 和 y 需要时间的最大值，特殊的，两格内的同行同列需要两步走到。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int x, y, X, Y;
    cin >> x >> y >> X >> Y;
    if (x == X && y == Y) {
        cout << 0;
        return;
    }
    int dx = abs(x - X);
    int dy = abs(y - Y);
    int n1 = (dx + 1) / 2;
    int n2 = (dy + 1) / 2;
    int ans = max(n1, n2);
    if (ans == 1) {
        if (x == X || y == Y)
            cout << 2;
        else {
            cout << 1;
        }
        return;
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}

J. Sichuan Provincial Contest

给一棵树，每个节点都有一个大写字母，问长度为 5 且节点恰好组成 SCCPC 的简单路径个数。

计数题

思路 1：枚举每个 C 节点，计数 SC+C+PC，答案为 SC 乘 PC。

首先算出每个节点来自儿子方向的 S 个数，C 个数，SC 个数，PC 个数。之后将 S 个数与 C 个数加上来自父亲方向的个数，变为每个节点各个方向的 S 与 C 个数。最后枚举每个 C 节点，总 SC 个数为儿子方向 + 父亲为 C 时父亲各个方向的 S 个数。总 PC 个数类似，注意减掉当前节点的一个 C。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e6 + 10, inf = 1e17;

ll n, S[N], C[N], SC[N], PC[N], ans;
string a;
vector<ll> e[N];

void dfs(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            continue;
        }
        dfs(son, root);
        if (a[son] == 'S') {
            S[root]++;
        }
        if (a[son] == 'C') {
            C[root]++;
            SC[root] += S[son];
        }
        if (a[son] == 'P') {
            PC[root] += C[son];
        }
    }
}

void dfs2(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            if (a[dad] == 'C') {
                C[root]++;
            }
            if (a[dad] == 'S') {
                S[root]++;
            }
            continue;
        }
        dfs2(son, root);
    }
}

void dfs3(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            continue;
        }
        dfs3(son, root);
    }
    if (a[root] == 'C') {
        ll dSC = 0, dPC = 0;
        if (a[dad] == 'C') {
            dSC += S[dad];
        }
        if (a[dad] == 'P') {
            dPC += C[dad] - 1;
        }
        ans += (SC[root] + dSC) * (PC[root] + dPC);
    }
}

void solve() {
    cin >> n >> a;
    a = " " + a;
    ans = 0;
    for (ll i = 1; i <= n; i++) {
        e[i].clear();
        S[i] = C[i] = SC[i] = PC[i] = 0;
    }
    for (ll i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    dfs3(1, 0);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    // T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

思路 2：计算每个节点儿子方向的 C PC CPC CCPC 个数。

对于每个 S 节点，答案加上儿子方向 CCPC 个数，之后如果父亲为 C，向父亲走，答案加上儿子方向 CPC 个数……注意走到 P 时，儿子方向 C 个数减一。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define int long long

vector<int> e[1000005];

int a[1000005];
int num[1000005][5]; // 1 21 121 1121

int fa[1000005];

void dfs(int x, int f)
{
    fa[x] = f;
    for (auto c : e[x])
    {
        if (c == f)
            continue;
        dfs(c, x);
        if (a[c] == 1) // C
        {
            num[x][1]++;
            num[x][3] += num[c][2];
            num[x][4] += num[c][3];
        }
        else if (a[c] == 2) // P
        {
            num[x][2] += num[c][1];
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        if (c == 'S')
            a[i] = 0;
        else if (c == 'C')
            a[i] = 1;
        else if (c == 'P')
            a[i] = 2;
        else
            a[i] = 114514;
    }
    for (int i = 1; i <= n; i++)
    {
        e[i].clear();
        num[i][0] = 0;
        num[i][1] = 0;
        num[i][2] = 0;
        num[i][3] = 0;
        num[i][4] = 0;
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, -1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != 0)
            continue;
        ans += num[i][4];
        int nex = fa[i];
        if (nex >= 1 && a[nex] == 1) // c
        {
            ans += num[nex][3];
            nex = fa[nex];
            if (nex >= 1 && a[nex] == 1) // c
            {
                ans += num[nex][2];
                nex = fa[nex];
                if (nex >= 1 && a[nex] == 2) // P
                {
                    ans += num[nex][1] - 1;
                    nex = fa[nex];
                    if (nex >= 1 && a[nex] == 1) // c
                    {
                        ans += 1;
                    }
                }
            }
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
    return 0;
}

A. Minimum Product

给定有向图，每条边有权值 \((a_i,b_i)\)，求从 1 到 n 的路径中，\((\sum a_i)\times(\sum b_i)\) 的最小值。

点数 \(1\le N\le 300\)，边数 \(1\le M \le 1000\)，权值 \(1\le a_i,b_i\le 200\)。

最短路动态规划设 \(f(i,j)\) 表示从 1 走到 \(i\) 点，a 权值和为 \(j\) 时 b 权值和的最小值。先枚举 a 权值和，然后枚举可行边转移（注意数组越界）。a 权值和的值域为 \(K=300·200\)，复杂度为 \(O(MK)\)。

比赛使用了 Dijkstra 加最优化剪枝（跑到 n 就记录答案，以后遇到更差的就不放入队列）。使用 Dij 复杂度高的原因是 Dij 是设想把原图的某点拆为走到某点并且 a 权值和为某值的点，优先队列内的元素个数为 \(NK\)，复杂度 \(O(NK\log (NK))\) 难以通过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 300 + 10, M = 300 * 200 + 300, inf = 1e14;

struct Data {
    ll u, v, a, b;
} e[M];
ll n, m, f[N][M];

void solve() {
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= M - 300; j++) {
            f[i][j] = inf;
        }
    }
    for (ll i = 1, u, v, a, b; i <= m; i++) {
        cin >> u >> v >> a >> b;
        e[i] = (Data) {u, v, a, b};
    }
    f[1][0] = 0;
    for (ll i = 0; i <= M - 300; i++) {
        for (ll j = 1; j <= m; j++) {
            f[e[j].v][i + e[j].a] = min(f[e[j].v][i + e[j].a], f[e[j].u][i] + e[j].b);
        }
    }
    ll ans = inf, ansa, ansb;
    for (ll i = 1; i <= M - 300; i++) {
        if (f[n][i] * i < ans) {
            ans = f[n][i] * i;
            ansa = i;
            ansb = f[n][i];
        }
    }
    cout << ansa << " " << ansb << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    // T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

（补题）C. Optimal Time

定义 \[ S(x) = \left\{d \mid d \mid x\right\} \cup \left\{kx \mid 2 \leq k \leq \left\lfloor \frac{N}{x} \right\rfloor \right\} \] 设当前状态为 \(x\)， \(x\) 可以选择等概率变成 \(S(x)\) 内的一个数，也可以选择不变。之后当前状态减 \(1\)。求从当前状态 \(x\) 变到 \(0\) 的期望次数。\(1\le N\le 10^5\)。

毒瘤题从 \(1\) 至 \(N\)，每个点 \(x\) 向 \(S(x)\) 连边，求 \(x\) 的期望步数 \(f(x)\) 为： \[ f(x)=\min\{f(x-1),\frac{\sum_{i\in S(x)}f(i-1)}{|S(x)|}\}+1 \] 但是这个转移方程显然存在后效性。解决方法是对这个过程迭代 100 次，可证明 \(f(x)\) 收敛。

比赛时想要探究 \(f(x)\) 是否有后效性，发现存在后效性后想通过某种方法去掉后效性，但是一筹莫展。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll M = 1e5 + 10, inf = 1e17;

ll N;
long double f[M];
vector<ll> e[M];

void init() {
    for (ll i = 1; i <= N; i++) {
        for (ll j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                e[i].push_back(j);
                if (j * j != i) {
                    e[i].push_back(i / j);
                }
            }
        }
        for (ll j = i * 2; j <= N; j += i) {
            e[i].push_back(j);
        }
    }
    for (ll i = 0; i <= N; i++) {
        f[i] = i;
    }
    for (ll k = 1; k <= 100; k++) {
        for (ll i = 1; i <= N; i++) {
            long double tmp = 0;
            for (auto j: e[i]) {
                tmp += f[j - 1];
            }
            f[i] = min(f[i - 1] + 1, tmp / e[i].size() + 1);
        }
    }
}

void solve() {
    ll x;
    cin >> x;
    cout << fixed << setprecision(6) << f[x] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> N >> T;
    init();
    while (T--) {
        solve();
    }
    return 0;
}

（补题）D. Tripartite Graph

给定一个排列 \(a_n\)，定义其生成图为 \(n\) 个节点，如果 \(i<j\land a_i>a_j\)，则存在无向边 \((i,j)\)。定义三分图为能够给所有节点染成三种颜色，使得每条无向边连接的两个节点颜色均不同。现在给定排列 \(q_n\)，问字典序大于 \(q_n\) 的排列的生成图有几个三分图。

\(T=300\) 个询问，\(1\le n\le 300\)。

点击查看题解

Dilworth 定理图为逆序对连边，所以如果最长下降子序列长度超过 3，必然存在节点个数等于 4 的子完全图使得无法三分染色（完全图任意节点都有连边，所以所有节点颜色必须均不相同）。而如果最长下降子序列长度不超过 3，一定可以被三分染色。

所以题意等价为寻找最长下降子序列不超过 3 的排列个数。根据 Dilworth 定理，等价于求可划分为三个上升子序列的排列个数。

判定是否可划分为三个上升子序列的方法是：令 \(a=b=c=0\)。从 \(1\) 至 \(n\)，

如果 \(q_i>c\)，则把 \(q_i\) 赋值给 \(c\)（安放）；
否则如果 \(q_i>b\)，安放；
否则如果 \(q_i>a\)，安放；
否则说明不可划分（不合法）。

如果最终都可安放，说明原序列可划分为三个上升子序列（合法），与此同时序列 \(c,b,a\) 也是原序列的一个最长下降子序列。

动态规划暂时不考虑大于排列 \(q_n\) 的做法。如果考虑设 \(f(a,b,c)\) 为最终得到的最长下降子序列为 \(c,b,a\) 的合法排列个数，则不容易写出转移方程（不容易维护未放置的数的集合）。

考虑设 \(f(u,v,w)\) 为在未放置的数中，大于 \(a\) 的个数为 \(u\)，……以此类推的合法排列个数。显然 \(u\ge v\ge w\)。

对于状态 \(f(u,v,w)\)，此时未安放的数属于 \([a,b]\) 的个数为 \(u-v\)，\([b,c]\) 为 \(v-w\)，\([c,n]\) 为 \(w\)。分类讨论接下来的三种情况：

接下来安放属于 \([c,n]\) 的某个数 \(c'\)。如果安放第 \(i\in[1,w]\) 个（从小到大），则大于 \(a,b\) 的个数均减一。而这个数一定安放在 \(c\)，也就是 \(c\) 变为这个数 \(c'\)。所以大于 \(c'\) 的个数为 \(w-i\)。所以 \(f(u,v,w)\) 可转移到 \(\forall i\in[1,w],f(u-1,v-1,w-i)\)。
接下来安放属于 \([b,c]\) 的某个数 \(b'\)。类似的，可转移到 \(\forall i\in[1,v-w],f(u-1,v-i,w)\)。
接下来安放属于 \([a,b]\) 的某个数 \(a'\)。如果安放的不是第一个（最小）未安放数字，则最小未安放数字在之后一定无处安放，导致排列不合法。所以，如果 \(u-v>0\)，只能转移到 \(f(u-1,v,w)\)。

前缀和设值域为 \(V\)，这样转移的复杂度为 \(O(V^4)\)，难以通过。设 \(g3(u,v,w)=\sum_{i=0}^w f(u,v,i)\)，\(g2(u,v,w)=\sum_{i=0}^v f(u,i,w)\)，通过前缀和可优化至 \(O(V^3)\)。

数位 DP 现在我们求出了所有的 \(f(u,v,w)\)。接下来考虑大于排列 \(q_n\) 的做法。利用数位 DP 的思想，可以枚举 \(q_n\) 的前缀 \(q[1:i],i\in[0,n]\)。

对于每个前缀 \(q[1:i]\)，其长度为 \(i\)。如果在 \(q[1:i]\) 的末尾穿插一个比 \(q_{i+1}\) 大的数字，那么长度为 \(n-i-1\) 的后缀就可以任取了。维护每个前缀的 \(a_i,b_i,c_i\)，同时维护对应的 \(u_i,v_i,w_i\)。记答案为 \(ans\)。跟上文动态规划部分很类似，

如果 \(q_{i+1}=a_{i+1}\lor q_{i+1}=b_{i+1}\lor q_{i+1}=c_{i+1}\)，\(q[1:i]\) 的末尾可以穿插一个比 \(\max(c_{i+1},q_{i+1})\) 大的某个数字，其数量为 \(w_{i+1}\)。 \(\forall j\in[1,w_{i+1}],ans\gets ans+f(u_i-1,v_i-1,w_{i+1}-j)\)
如果 \(q_{i+1}=a_{i+1}\lor q_{i+1}=b_{i+1}\)，\(q[1:i]\) 的末尾可以穿插一个比 \(\max(b_{i+1},q_{i+1})\) 大并且比 \(c_{i+1}\) 小的某个数字，其数量为 \(v_{i+1}-w_{i+1}\)。 \(\forall j\in[1,v_{i+1}-w_{i+1}],ans\gets ans+f(u_i-1,v_{i+1}-j,w_i)\)
如果 \(q_{i+1}=a_{i+1}\)，不能改为安放比 \(\max(a_{i+1},q_{i+1})\) 大并且比 \(b_{i+1}\) 小的某个数字，否则 \(q_{i+1}\) 在之后一定无处安放，导致排列不合法，此步不可转移。 \(ans\gets ans+0\)

这一部分时间复杂度为 \(O(n^2)\)。

总时间复杂度为 \(O(V^3+Tn^2)\)，可以通过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 300 + 10, inf = 1e17, mod = 998244353;

ll n, a[N], f[N][N][N], g3[N][N][N], g2[N][N][N];

ll dfs(ll u, ll v, ll w) {
    if (f[u][v][w]) {
        return f[u][v][w];
    }
    if (u == 0 && v == 0 && w == 0) {
        return f[u][v][w] = 1;
    }
    ll ret = 0;
    ll f1 = u - v, f2 = v - w, f3 = w;
    ll i = 1;
    for (i = 1; i <= f3; i++) {
        if (g3[u - 1][v - 1][w - i]) {
            ret = (ret + g3[u - 1][v - 1][w - i]) % mod;
            break;
        } else {
            ret = (ret + dfs(u - 1, v - 1, w - i)) % mod;
        }
    }
    for (; i >= 1; i--) {
        if (w - i >= 1) {
            g3[u - 1][v - 1][w - i] = (f[u - 1][v - 1][w - i] + g3[u - 1][v - 1][w - i - 1]) % mod;
        } else if (w - i == 0) {
            g3[u - 1][v - 1][w - i] = f[u - 1][v - 1][w - i];
        }
    }
    for (i = 1; i <= f2; i++) {
        if (g2[u - 1][v - i][w]) {
            ret = (ret + g2[u - 1][v - i][w]) % mod;
            break;
        } else {
            ret = (ret + dfs(u - 1, v - i, w)) % mod;
        }
    }
    for (; i >= 1; i--) {
        if (v - i >= w + 1) {
            g2[u - 1][v - i][w] = (f[u - 1][v - i][w] + g2[u - 1][v - i - 1][w]) % mod;
        } else if (v - i == w) {
            g2[u - 1][v - i][w] = f[u - 1][v - i][w];
        }
    }
    if (f1 >= 1) {
        ret = (ret + dfs(u - 1, v, w)) % mod;
    }
    return f[u][v][w] = ret;
}

void solve() {
    ll ans = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ll pu = n, pv = n, pw = n;
    ll n1 = 0, n2 = 0, n3 = 0;
    for (ll i = 1; i <= n; i++) {
        if (a[i] > n3) {
            n3 = a[i];
        } else if (a[i] > n2) {
            n2 = a[i];
        } else if (a[i] > n1) {
            n1 = a[i];
        } else {
            break;
        }
        ll u = 0, v = 0, w = 0;
        for (ll j = i + 1; j <= n; j++) {
            if (a[j] > n3) {
                u++, v++, w++;
            } else if (a[j] > n2) {
                u++, v++;
            } else if (a[j] > n1) {
                u++;
            }
        }
        ll f1 = u - v, f2 = v - w, f3 = w;
        if (a[i] == n3 || a[i] == n2 || a[i] == n1) {
            for (ll j = 1; j <= f3; j++) {
                ans = (ans + f[pu - 1][pv - 1][w - j]) % mod;
            }
        }
        if (a[i] == n2 || a[i] == n1) {
            for (ll j = 1; j <= f2; j++) {
                ans = (ans + f[pu - 1][v - j][pw]) % mod;
            }
        }
        pu = u, pv = v, pw = w;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    dfs(300, 300, 300);
    while (T--) {
        solve();
    }
    return 0;
}

（补题）L. abc

给定长度为 \(n=2\times10^5\) 且只含有字符 abc 的字符串 \(S\)。定义 \(val(S)\) 为出现次数最多的字符的出现次数减出现次数最少的字符的出现次数。求 \(\sum_{i=1}^n\sum_{j=i}^n val(S[i,j])\)。

点击查看题解

计数题前缀和容斥如果只有两个字符 ab，可以令 \(a=1,b=-1\)，计算前缀和 \(T\)，则答案为 \(\sum_{i=0}^n\sum_{j=i}^n |T_i-T_j|\)。\(O(n\log n)\) 的计算方法为对 \(T_i\) 排序，则第 \(i\) 小的 \(T_i'\) 在求和式子展开后的系数为 \((i-1)-(n-i)=2i-n-1\)。

此时会认为一字符区间的答案是区间长度（应当为 \(0\)），需要减去。方法为找出所有极长的一字符区间（例如 aaabaa 为 aaa，b，aa），设长度为 \(L\)，则减掉 \(\sum_{i=1}^L i(L-i+1)\)。

现在有三个字符 abc，可以分别令 \((a,b,c)=(1,-1,0),(1,0,-1),(0,1,-1)\)，计算前缀和 \(A,B,C\)，则答案为 \(\sum_{i=0}^n\sum_{j=i}^n \max\{|A_i-A_j|,|B_i-B_j|,|C_i-C_j|\}\)。

但是如何处理 \(\max\) 呢？比赛时候没有想到好的解决方法。实际上，令 \(a,b,c\) 为区间 \([i,j]\) 的 abc 个数： \[ \begin{cases} |A_i-A_j|=|a-b|\\ |B_i-B_j|=|a-c|\\ |C_i-C_j|=|b-c|\\ \max\{|a-b|,|a-c|,|b-c|\}=(|a-b|+|a-c|+|b-c|)/2\\ \end{cases}\\ \implies\max\{|A_i-A_j|,|B_i-B_j|,|C_i-C_j|\}=(|A_i-A_j|+|B_i-B_j|+|C_i-C_j|)/2 \] 但是这样求不完全符合题意。具体是：

三字符区间：符合题意。
二字符区间：认为最少出现次数为 \(0\)，需要减掉实际最少出现次数 \(\min\)。
一字符区间：认为最少出现次数为 \(0\)，直接去除此区间贡献即可。

下文令 \(F(Arr,l,r)=\sum_{i=l-1}^r\sum_{j=i}^r |Arr_i-Arr_j|,G(L)=\sum_{i=1}^L i(L-i+1)\)。

三字符区间贡献为 \((F(A,1,n)+F(B,1,n)+F(C,1,n))/2\)。

需要减去二字符区间贡献。找出所有极长的只含有 ab 的二字符区间（例如 aaabcbba 为 aaab，bba）。对于每个极长区间 \([l_i,r_i]\)，

计算 \(F(A,l_i,r_i)\)，这样算出来包含二字符区间的正确答案 \(\max-\min\) 与一字符区间的多余贡献；
计算 \(G(r_i-l_i+1)\)，这样算出来包含二字符区间的 \(\max+\min\)（即区间长度）与一字符区间的多余贡献。

\((G(r_i-l_i+1)-F(A,l_i,r_i))/2\) 为二字符区间的 \(((\max-\min)-(\max+\min))/2=\min\)，即需要减去的二字符区间贡献；而一字符区间的多余贡献恰好抵消。之后对于 bc，ac 再做一次即可。

需要减去一字符区间贡献。方法与上面所说只有二字符时的情况类似，即找出所有极长的一字符区间，设长度为 \(L_i\)，则减掉 \(G(L_i)\)。

所以最终答案为： \[ \begin{aligned} &\frac{1}{2}(F(A,1,n)+F(B,1,n)+F(C,1,n))\\ -&\sum_{i\in A}\frac{(G(r_i-l_i+1)-F(A,l_i,r_i))}{2}\\ -&\sum_{i\in B}\frac{(G(r_i-l_i+1)-F(B,l_i,r_i))}{2}\\ -&\sum_{i\in C}\frac{(G(r_i-l_i+1)-F(C,l_i,r_i))}{2}\\ -&\sum_{i}G(L_i) \end{aligned} \]