AtCoder Beginner Contest 455 题解

for-each2026年8月18日大约 22 分钟

AtCoder Beginner Contest 455 题解

项目	内容
比赛时间	2026-04-25
比赛链接	https://atcoder.jp/contests/abc455
题目数量	A–G 共 7 题

比赛概览

本场难度梯度非常清晰：A、B 是纯签到题（一个条件判断、一个四重循环暴力枚举）；C 是"贪心 + 计数"（按 $x\cdot c_x$ 取前 $K$ 大）；D 是用 up/down 数组在 $O(1)$ 内维护"整叠移动"的经典链表题，值得细品；E 是"容斥 + 前缀差分"的字符串计数；F 的关键观察是合并史莱姆的总代价与合并顺序无关，配合懒标记线段树维护区间和与区间平方和；G 是压轴的难题，需要滑动窗口 + 随机哈希，在 $O(KN)$ 内分别统计两类"平衡子数组"。其中 D、F、G 三题较有区分度，是值得重点掌握的考点。

A - 455

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_a

题目大意

给定三个整数 $A, B, C$ （ $1\le A,B,C\le 9$ ）。若 $A \neq B$ 且 $B = C$ ，输出 Yes，否则输出 No。

思路

没有任何技巧，直接按题意把两个条件翻译成代码即可：

条件一： $A \neq B$ ；
条件二： $B = C$ ；

两者同时满足（逻辑与）时输出 Yes，否则输出 No。

易错点：注意是比较 $B$ 与 $C$ 是否相等，而不是 $A$ 与 $C$ ；条件一是"不相等"，条件二是"相等"，方向别写反。示例 3 中 $6,6,6$ 因为 $A=B$ 而不满足条件一，输出 No。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A != B && B == C) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

官方题解还给出了等价的 Python 写法：

a, b, c = map(int, input().split())
print("Yes" if a != b and b == c else "No")

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Spiral Galaxy

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_b

题目大意

有一个 $H$ 行 $W$ 列的网格，. 表示白格、# 表示黑格。称一个矩形区域是"点对称染色"的，如果区域内任意格子 $(i,j)$ 与它关于矩形中心对称的格子 $(h_1+h_2-i,\ w_1+w_2-j)$ 颜色相同。求满足条件的矩形区域个数（ $1\le H,W\le 10$ ）。

思路

$H,W \le 10$ 意味着矩形的数量至多

\frac{H(H+1)}{2}\cdot\frac{W(W+1)}{2} \le \frac{10\cdot 11}{2}\cdot\frac{10\cdot 11}{2}=3025

直接暴力即可：用四重循环枚举矩形的上边 $h_1$ 、下边 $h_2$ 、左边 $w_1$ 、右边 $w_2$ ，再检查区域内所有格子是否满足点对称条件。

点对称的含义：矩形中心位于 $((h_1+h_2)/2,\ (w_1+w_2)/2)$ ，格子 $(i,j)$ 的对称格为

(i',j')=(h_1+h_2-i,\ w_1+w_2-j)

条件要求 $S_i[j]=S_{i'}[j']$ 对所有区域内 $(i,j)$ 成立。注意到 $(i',j')$ 的对称格恰好是 $(i,j)$ ，所以即便把所有格子的配对重复检查两次也不影响正确性；实现时可以对区域内每个格子直接比较，一旦发现不匹配就判定失败、提前退出。

为什么正确：四重循环穷举了所有可能的矩形（每个 $(h_1,h_2,w_1,w_2)$ 唯一对应一个矩形），对每个矩形都完整地验证了点对称条件，因此计数不重不漏。

复杂度：最坏情况下检查的总格点数等于

\sum_{\text{矩形}}\text{面积}=\binom{H+2}{3}\binom{W+2}{3} \le \binom{12}{3}^2=220^2=48400

完全可行。实现时用字符比较即可，注意下标从 0 开始。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    long long ans = 0;
    for (int h1 = 0; h1 < H; h1++)
        for (int h2 = h1; h2 < H; h2++)
            for (int w1 = 0; w1 < W; w1++)
                for (int w2 = w1; w2 < W; w2++) {
                    bool ok = true;
                    for (int i = h1; i <= h2 && ok; i++)
                        for (int j = w1; j <= w2 && ok; j++) {
                            int ii = h1 + h2 - i, jj = w1 + w2 - j;
                            if (S[i][j] != S[ii][jj]) ok = false;
                        }
                    if (ok) ans++;
                }
    cout << ans << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(H^3W^3)$ （ $H,W\le 10$ 时实际检查约 $48400$ 次）
空间复杂度： $O(HW)$

C - Vanish

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_c

题目大意

给定长度为 $N$ 的整数序列 $A$ 与操作次数 $K$ 。一次操作：选定整数 $x$ ，把 $A$ 中所有等于 $x$ 的元素变为 $0$ 。执行恰好 $K$ 次操作后，求序列元素和的最小可能值。 $1\le K\le N\le 3\times10^5$ ， $1\le A_i\le 10^9$ 。

思路

关键观察：一次选择 $x$ 的操作，效果等价于"把数值为 $x$ 的元素从序列中全部删掉"。设 $c_x$ 为 $x$ 在 $A$ 中出现的次数，则对 $x$ 做一次操作能让总和减少

x\cdot c_x

由于每次操作必须选定一个 $x$ ，而不同 $x$ 之间互不影响（删除 $x$ 不会改变其它数值的出现次数），所以为了让最终和最小，应当把 $K$ 个"收益" $x\cdot c_x$ 中最大的 $K$ 个对应数值各操作一次。

为什么正确：

对同一个 $x$ 操作两次是无意义的（第一次已把它全部清零，第二次无任何效果），所以最优解中每个 $x$ 至多被选一次；
收益之间相互独立，总和减少量等于被选数值的 $x\cdot c_x$ 之和，因此等价于从集合 $\{x\cdot c_x\}$ 中选 $K$ 个最大的；
若不同数值的个数不足 $K$ ，多余的次数可以选一个"从未出现过的 $x$ "来完成操作（此时没有任何元素变为 0，序列不变），不影响结果。

因此答案 = 原始总和 − 前 $\min(K,\ \text{不同数值个数})$ 大的 $x\cdot c_x$ 之和。

实现： $A_i$ 可达 $10^9$ ，不能用普通数组计数，用 map（或对排序后的 $A$ 做游程压缩）统计每个数值的出现次数，得到向量 $\{x\cdot c_x\}$ 后降序排序、减去前 $K$ 项即可。注意答案用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    map<ll, ll> cnt;
    ll total = 0;
    for (int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        cnt[a]++;
        total += a;
    }
    vector<ll> gain;
    for (auto& [x, c] : cnt) gain.push_back(x * c);
    sort(gain.rbegin(), gain.rend());
    for (int i = 0; i < K && i < (int)gain.size(); i++) total -= gain[i];
    cout << total << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （map 计数 + 排序）
空间复杂度： $O(N)$

D - Card Pile Query

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_d

题目大意

有 $N$ 张牌和 $N$ 叠牌，初始时第 $i$ 叠只有牌 $i$ 。依次执行 $Q$ 个操作：把牌 $C_i$ 以及它上面的所有牌（保持相对顺序）整叠移动到牌 $P_i$ 的上方。保证操作前 $C_i$ 与 $P_i$ 在不同叠中，且 $P_i$ 在某叠的顶部。问全部操作结束后每叠各有多少张牌。 $N,Q\le 3\times10^5$ 。

思路

若朴素维护"每叠的牌序列"，一次移动可能搬动一叠里的很多牌，总复杂度会退化成 $O(NQ)$ ，不可行。

关键观察：我们只在结束时需要每叠的张数，不需要中间过程。而"把 $C$ 顶上的一整块挪到 $P$ 上"本质上是把一个栈拆开、接到另一个栈上——用两个数组精确记录"每张牌上下相邻是谁"即可在 $O(1)$ 内完成。

定义两个数组（下标 $0..2N-1$ ）：

up[i]：牌 $i$ 上方的牌（没有则为 $-1$ ）；
down[i]：牌 $i$ 下方的牌（没有则为 $-1$ ）。

为了让"某叠空了"这个状态也能自然表达，给第 $i$ 叠底部放一张永远不会被移动的哨兵牌 $N+i$ 。初始化时：

\text{up}[N+i]=i,\qquad \text{down}[i]=N+i

即哨兵在底、牌 $i$ 在哨兵上方。

一次操作 $(C,P)$ 中，设 $D=\text{down}[C]$ （ $C$ 下方的牌）。把以 $C$ 为底的整块从 $D$ 上方拆下、接到 $P$ 上方，只需三步：

\text{down}[C]\gets P,\qquad \text{up}[P]\gets C,\qquad \text{up}[D]\gets -1

$C$ 上方那一块的内部关系完全不变，无需任何修改。

为什么正确：

操作前 $P$ 必在某叠顶部，故 $\text{up}[P]=-1$ ，把 $C$ 接到 $P$ 上方合法；
$D$ 是 $C$ 原来的下方邻牌，拆走后 $D$ 上方不再有牌，故 $\text{up}[D]=-1$ ；
哨兵永不参与移动：当 $C$ 是某叠的底牌时 $D$ 就是该叠的哨兵，更新后哨兵的 up 变为 $-1$ ，表示该叠为空；
由于每张牌的 up/down 只与它的直接上下邻牌有关， $O(1)$ 次修改就完整刻画了新状态。

结束时，从第 $i$ 叠的哨兵 $N+i$ 出发沿 up 指针向上走，走过的牌数就是该叠的牌数。每条链（每叠）恰好被遍历一次，总代价 $O(N)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> up(2 * N, -1), down(2 * N, -1);
    for (int i = 0; i < N; i++) {
        up[N + i] = i;       // 第 i 叠的哨兵 N+i 上方是牌 i
        down[i] = N + i;     // 牌 i 下方是它所在叠的哨兵
    }
    while (Q--) {
        int c, p;
        cin >> c >> p;
        c--; p--;
        int d = down[c];
        down[c] = p;   // C 接到 P 上方
        up[p] = c;
        up[d] = -1;    // D 上方没有牌了
    }
    for (int i = 0; i < N; i++) {
        int x = N + i, ans = 0;
        while (up[x] != -1) {
            x = up[x];
            ans++;
        }
        cout << ans << (i + 1 == N ? "\n" : " ");
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N+Q)$ （每个操作 $O(1)$ ，结束时每条牌链遍历一次）
空间复杂度： $O(N)$

E - Unbalanced ABC Substrings

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_e

题目大意

给定长度 $N$ 、只含 A、B、C 三种字符的字符串 $S$ （ $N\le 2\times10^5$ ）。求有多少个非空子串满足：A、B、C 在其中的出现次数两两不同。位置不同即视为不同子串。

思路

设子串中 A、B、C 的出现次数分别为 $A,B,C$ （稍后会看到上下文区分）。"两两不同"即 $A\ne B$ 、 $A\ne C$ 、 $B\ne C$ 三个条件同时成立。直接用容斥原理处理"不等"比较麻烦，转而对相等事件做容斥。

设 $f(A{=}B)$ 表示满足"出现次数 $A=B$ "的子串个数，其余同理， $f(A{=}B{=}C)$ 表示三者全相等的子串个数。全部非空子串数为 $\dfrac{N(N+1)}{2}$ 。对"三个相等条件全部不成立"作容斥：

\text{ans}=\frac{N(N+1)}{2}-f(A{=}B)-f(A{=}C)-f(B{=}C)+3f(A{=}B{=}C)-f(A{=}B{=}C)

其中第二项到第四项来自： $E_{AB}\cap E_{AC}=E_{ABC}$ 等三组两两交，均等于 $A{=}B{=}C$ ，而三交集也是 $A{=}B{=}C$ 。化简得：

\text{ans}=\frac{N(N+1)}{2}-f(A{=}B)-f(A{=}C)-f(B{=}C)+2\,f(A{=}B{=}C)

如何统计 $f(A{=}B)$ ：设 $pA_i,pB_i$ 分别为前 $i$ 个字符中 A、B 的个数（ $0\le i\le N$ ），则子串 $(l, r]$ （第 $l+1$ 到第 $r$ 个字符）中 A、B 的出现次数分别为 $pA_r-pA_l$ 、 $pB_r-pB_l$ 。于是

pA_r-pA_l=pB_r-pB_l \iff (pA_l-pB_l)=(pA_r-pB_r)

所以只需对每个前缀下标 $i$ 计算差值 $d_i=pA_i-pB_i$ ，然后统计"有多少对 $(l,r)$ 的 $d_l=d_r$ "：若某个值出现 $c$ 次，则贡献 $\dbinom{c}{2}$ 。 $f(A{=}C)$ 、 $f(B{=}C)$ 同理。

$f(A{=}B{=}C)$ ：三个相等等价于两个独立条件同时成立，例如

pA_r-pA_l=pB_r-pB_l \ \text{且}\ pA_r-pA_l=pC_r-pC_l

等价于二元组 $(pA_l-pB_l,\ pA_l-pC_l)=(pA_r-pB_r,\ pA_r-pC_r)$ 。对每个 $i$ 计算二元组，用哈希表统计每种二元组出现次数 $c$ ，累加 $\dbinom{c}{2}$ 即可。

复杂度：前缀差值范围在 $[-N,N]$ 内，单值用 unordered_map、二元组用 map（或自定义哈希的 unordered_map）均可，总复杂度 $O(N)$ 或 $O(N\log N)$ 。

参考代码

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

// 统计前缀差数组中相同值出现的对数 sum C(c,2)
ll countEqual(const vector<ll>& key) {
    unordered_map<ll, ll> freq;
    for (ll x : key) freq[x]++;
    ll res = 0;
    for (auto& [k, c] : freq) res += c * (c - 1) / 2;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    string S;
    cin >> N >> S;
    ll total = (ll)N * (N + 1) / 2;

    vector<int> pA(N + 1, 0), pB(N + 1, 0), pC(N + 1, 0);
    for (int i = 0; i < N; i++) {
        pA[i + 1] = pA[i] + (S[i] == 'A');
        pB[i + 1] = pB[i] + (S[i] == 'B');
        pC[i + 1] = pC[i] + (S[i] == 'C');
    }
    vector<ll> keyAB(N + 1), keyAC(N + 1), keyBC(N + 1);
    for (int i = 0; i <= N; i++) {
        keyAB[i] = (ll)(pA[i] - pB[i]);
        keyAC[i] = (ll)(pA[i] - pC[i]);
        keyBC[i] = (ll)(pB[i] - pC[i]);
    }
    ll fAB = countEqual(keyAB);
    ll fAC = countEqual(keyAC);
    ll fBC = countEqual(keyBC);

    map<pair<ll, ll>, ll> freq;
    for (int i = 0; i <= N; i++) freq[{keyAB[i], keyAC[i]}]++;
    ll fABC = 0;
    for (auto& [pr, c] : freq) fABC += c * (c - 1) / 2;

    ll ans = total - fAB - fAC - fBC + 2 * fABC;
    cout << ans << "\n";
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （二元组用 map；若自定义哈希可到期望 $O(N)$ ）
空间复杂度： $O(N)$

F - Merge Slimes 2

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_f

题目大意

有一个长度 $N$ 、初始全 0 的序列 $A$ 。依次处理 $Q$ 个查询，每个查询给定 $l_q,r_q,a_q$ ：

先把 $a_q$ 加到 $A_{l_q},A_{l_q+1},\dots,A_{r_q}$ 上；
记 $M=r_q-l_q+1$ ， $B=(B_1,\dots,B_M)=(A_{l_q},\dots,A_{r_q})$ 。有 $M$ 只重量分别为 $B_m$ 的史莱姆，每次合并两只重量为 $x,y$ 的史莱姆，代价为 $x\times y$ ，新史莱姆重量 $x+y$ 。求合并 $M-1$ 次的最小总代价（对 $998244353$ 取模）。

$N,Q\le 10^5$ ， $a_q\le 10^9$ ，且对 $A$ 的修改会保留到后续查询。

思路

1. 关键观察：总代价与合并顺序无关

这是本题的核心。把每只史莱姆想象成 $B_m$ 个人（ $m=1..M$ ）。一次合并两只史莱姆的代价 $x\times y$ ，恰好等于"两群人之间的配对数量"。

考虑任意一对人 $(X,Y)$ ：如果 $X,Y$ 最初属于同一只史莱姆，那么它们在全部 $M-1$ 次合并中永远不会成为"不同群之间的配对被计入"的对象；如果 $X,Y$ 最初属于不同的史莱姆，那么它们各自所在的群在某一次合并中恰好第一次合到一起，就在那一刻被计入一次，之后它们一直同群，不再被计入。因此：

\text{总代价}=\sum_{\text{不同初群的人对 }(X,Y)}1=\frac{\left(\sum_{m=1}^{M}B_m\right)^2-\sum_{m=1}^{M}B_m^2}{2}

（总对数减去同群的对数再除以 2，即 $\sum_{i<j}B_iB_j$ 。）由于每一对人被计入的次数与合并顺序无关，总代价与合并顺序无关，所以"最小总代价"就是上式本身。

2. 问题转化为区间求和

于是每个查询的答案只取决于两样东西：

S=\sum_{i=l}^{r}A_i,\qquad Q=\sum_{i=l}^{r}A_i^2,\qquad \text{ans}=\frac{S^2-Q}{2}\pmod{998244353}

需要支持两种操作：

区间整体加一个值 $a$ ；
查询区间和 $S$ 与区间平方和 $Q$ 。

用懒标记线段树即可。对每个节点维护 $len$ （区间长度）、 $sum$ 、 $sumsq$ 。对整段加 $a$ 时：

sum' = sum + a\cdot len

sumsq' = \sum(A_i+a)^2 = sumsq + 2a\sum A_i + a^2\cdot len = sumsq + 2a\cdot sum + a^2\cdot len

因为 $A_i$ 会随查询累加变得很大（可达 $10^{14}$ ），但所有量都只在模 $998244353$ 下使用，且答案本身是 $A_i$ 的整系数多项式，所以全程在模意义下维护 $sum,sumsq$ 即可，除以 2 用逆元 $2^{-1}\equiv \frac{998244353+1}{2}$ 。

实现细节：push 时按左右子区间的长度分别应用懒标记；a^2*len 与 2a*sum 用 long long 计算后取模（中间值不超过约 $10^{18}$ ，在 64 位范围内）。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

struct SegTree {
    int n;
    vector<ll> sum, sumsq, lazy;   // 均按模 MOD 维护
    SegTree(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        sum.assign(2 * n, 0);
        sumsq.assign(2 * n, 0);
        lazy.assign(2 * n, 0);
    }
    void apply(int node, int len, ll a) {
        a %= MOD;
        sumsq[node] = (sumsq[node] + 2 * a % MOD * sum[node] + a * a % MOD * len) % MOD;
        sum[node] = (sum[node] + a * len) % MOD;
        lazy[node] = (lazy[node] + a) % MOD;
    }
    void push(int node, int llen, int rlen) {
        if (lazy[node]) {
            apply(node * 2, llen, lazy[node]);
            apply(node * 2 + 1, rlen, lazy[node]);
            lazy[node] = 0;
        }
    }
    void range_add(int node, int nl, int nr, int ql, int qr, ll a) {
        if (qr < nl || nr < ql) return;
        if (ql <= nl && nr <= qr) { apply(node, nr - nl + 1, a); return; }
        int mid = (nl + nr) / 2;
        push(node, mid - nl + 1, nr - mid);
        range_add(node * 2, nl, mid, ql, qr, a);
        range_add(node * 2 + 1, mid + 1, nr, ql, qr, a);
        sum[node] = (sum[node * 2] + sum[node * 2 + 1]) % MOD;
        sumsq[node] = (sumsq[node * 2] + sumsq[node * 2 + 1]) % MOD;
    }
    pair<ll, ll> query(int node, int nl, int nr, int ql, int qr) {
        if (qr < nl || nr < ql) return {0, 0};
        if (ql <= nl && nr <= qr) return {sum[node], sumsq[node]};
        int mid = (nl + nr) / 2;
        push(node, mid - nl + 1, nr - mid);
        auto L = query(node * 2, nl, mid, ql, qr);
        auto R = query(node * 2 + 1, mid + 1, nr, ql, qr);
        return {(L.first + R.first) % MOD, (L.second + R.second) % MOD};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    SegTree st(N);
    const ll inv2 = (MOD + 1) / 2;   // 2 的模逆元
    while (Q--) {
        int l, r;
        ll a;
        cin >> l >> r >> a;
        l--; r--;
        st.range_add(1, 0, st.n - 1, l, r, a % MOD);
        auto [S, Q2] = st.query(1, 0, st.n - 1, l, r);
        ll ans = ((S * S - Q2) % MOD + MOD) % MOD;   // 注意取非负
        ans = ans * inv2 % MOD;
        cout << ans << "\n";
    }
    return 0;
}

复杂度分析

时间复杂度： $O((N+Q)\log N)$
空间复杂度： $O(N)$

G - Balanced Subarrays

题目链接：https://atcoder.jp/contests/abc455/tasks/abc455_g

题目大意

给定长度为 $N$ 的正整数序列 $A$ （ $1\le A_i\le N$ ）。一个非空连续子数组称为平衡的，如果其中每个出现过的整数出现的次数都相同。对每个 $k=1,\dots,K$ （ $K\le \min(N,10)$ ），求：

$c_{k,1}$ ：每个出现过的整数恰好出现 $B_k$ 次的平衡子数组个数；
$c_{k,2}$ ：恰好包含 $B_k$ 种不同整数的平衡子数组个数。

共 $T$ 组测试， $\sum N\le 2\times10^5$ 。位置不同即视为不同子数组。

思路

两类计数相互独立，分别处理。为叙述方便，固定一个 $B=B_k$ 。

第一部分：每个出现值恰好出现 $B$ 次（ $c_{k,1}$ ）

条件转化。子数组 $(l,r]$ （第 $l+1$ 到第 $r$ 个位置）中每个出现值恰好出现 $B$ 次，等价于：

每个值的出现次数 $\le B$ ；
每个值的出现次数 $\equiv 0 \pmod B$ 。

（若出现次数 $c$ 满足 $1\le c\le B$ 且 $B\mid c$ ，则只能 $c=B$ 。）

条件 1 用滑动窗口。固定右端 $r$ ，维护指针 $\text{ptr}$ 使得窗口 $[\text{ptr}, r-1]$ 中每个值的出现次数都不超过 $B$ ，且 $\text{ptr}$ 是最小的这样的左端。于是所有满足条件 1 的左端 $l$ 恰为 $l\in[\text{ptr}, r-1]$ 。每增加一个 $r$ ，只有新加入的 $A_{r-1}$ 可能超限，用它驱动 while 循环右移 $\text{ptr}$ ，总代价 $O(N)$ 。

条件 2 用随机哈希。选取一个大素数模数 $M$ （如 $998244353$ ）。对每个值 $v$ ，生成 $B$ 个随机数 $w_{v,0},w_{v,1},\dots,w_{v,B-1}$ ，要求

\sum_{j=0}^{B-1} w_{v,j}\equiv 0\pmod M

把 $v$ 的第 $t$ 次出现（ $0$ 基序号）赋值为 $w_{v,\,t\bmod B}$ 。定义前缀哈希

H_i=\sum_{j<i} h_j\pmod M

其中 $h_j$ 是位置 $j$ 上赋的值。则子数组 $(l,r]$ 的哈希为 $H_r-H_l\pmod M$ 。

看单个值 $v$ 的贡献：它在子数组中出现了 $c$ 次，对应的是一段长度为 $c$ 的连续序号区间，其贡献是循环序列 $w_{v,\cdot}$ 上连续 $c$ 项之和。若 $B\mid c$ ，这段恰好完整覆盖每个余数 $c/B$ 次，贡献为 $\frac{c}{B}\cdot\sum_j w_{v,j}\equiv 0$ ；若 $B\nmid c$ ，它覆盖的是余数环上的一段"真子区间"，贡献是一个随机值，几乎不可能为 0。因此

H_r\equiv H_l\pmod M \iff \text{所有值的出现次数都被 } B \text{ 整除（概率极高）}

计数。对每个 $r$ ，在 $l\in[\text{ptr},r-1]$ 中数出满足 $H_l\equiv H_r\pmod M$ 的个数。这可以通过一边扫描一边维护 H_l 的频率表完成：右端前进时把 $H_{r}$ 加入频率表， $\text{ptr}$ 右移时把 $H_{\text{ptr}}$ 从表中删去，然后查询 freq[H_r]。每个下标至多入表、出表各一次，总 $O(N)$ 。

关于生成 $w_{v,j}$ 的实现：若 $v$ 出现次数 $c\ge B$ ，生成全部 $B$ 个值（最后一个取负和）；若 $c<B$ ，则被用到的余数只有 $0..c-1$ （此时连续区间不会环绕），直接生成 $c$ 个自由随机数即可。对每个 $B$ 值总共生成 $O(N)$ 个随机数。

第二部分：恰好包含 $B$ 种不同值（ $c_{k,2}$ ）

左端区间与唯一集合。固定右端 $r$ ，令 $f(l)$ 为 $A_l..A_{r-1}$ 中不同值的个数。 $f(l)$ 关于 $l$ 单调不增（左端右移只会删元素，不同值个数不会增加），所以满足 $f(l)=B$ 的 $l$ 构成一个连续区间 $[L_r,U_r]$ 。进一步，由于左端右移只会让"集合"减少而不会引入新值，区间内所有 $l$ 对应的不同值集合完全相同。称这个唯一集合的哈希为 $H$ 。

给每个整数值 $v$ 分配随机数 $R_v$ ，令前缀和

S_i=\sum_{j<i} R_{A_j}\pmod M

子数组 $(l,r]$ 长度为 $r-l$ ，若它恰好含 $B$ 种不同值（集合哈希 $H$ ）且平衡，设每种值都出现 $t$ 次，则 $r-l=Bt$ ，且

S_r-S_l=\sum_{v\in\text{集合}}t\cdot R_v=t\cdot H\pmod M

反之亦然（哈希冲突概率可忽略）。把 $t=(r-l)/B$ 代入并移项：

B\cdot S_r-H\cdot r\equiv B\cdot S_l-H\cdot l\pmod M

即对 $F_i\equiv B\cdot S_i-H\cdot i\pmod M$ ，需满足 $F_r\equiv F_l$ 。所以 $c_{k,2}$ 等于：对每个 $r$ ，在 $l\in[L_r,U_r]$ 中数出 $F_l\equiv F_r$ 的个数。

频率表的维护。当 $r$ 递增时， $[L_r,U_r]$ 的左右端点都单调不降。若集合（哈希 $H$ ）不变，则 $F$ 是同一条线性函数，频率表可增量维护：删去 $[L_{\text{old}},L_r-1]$ 、加入 $[U_{\text{old}}+1,U_r]$ 。若集合改变，需要按新 $H$ 重建频率表。关键性质：集合改变时必有 $L_r>U_{\text{old}}$ ——否则新旧区间在 $l$ 上有公共部分，公共部分对应的子数组同时属于两个集合，只能同集合，矛盾。因此重建涉及的左端下标全部大于旧区间右端点，每个下标在整个过程中至多入表一次，重建总代价 $O(N)$ 。

实现要点：用两个双指针分别维护 $L_r$ （最小左端，保持"不同值个数 $\le B$ "）与 $U_r$ （最大左端，保持"不同值个数 $\ge B$ "）；集合哈希随 $L$ 窗口的进出实时维护。若 $B$ 大于整个序列的不同值个数，答案为 0。

综合复杂度：对每个 $k$ 两类统计各 $O(N)$ 次哈希表操作，共 $K$ 轮，故期望 $O(KN)$ （最坏 $O(KN\log N)$ ，取决于哈希表实现）。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll rnd64() {
    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return rng() % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        vector<int> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        vector<int> B(K);
        for (int i = 0; i < K; i++) cin >> B[i];

        // 每个值的出现次数，以及每个位置在该值内的出现序号（0 基）
        vector<int> cntv(N + 1, 0);
        for (int x : A) cntv[x]++;
        vector<int> rank(N);
        {
            vector<int> cur(N + 1, 0);
            for (int i = 0; i < N; i++) rank[i] = cur[A[i]]++;
        }
        // 每个整数值一个随机"集合哈希"
        vector<ll> R(N + 1);
        for (int v = 1; v <= N; v++) R[v] = rnd64();
        vector<ll> S(N + 1, 0);
        for (int i = 0; i < N; i++) S[i + 1] = (S[i] + R[A[i]]) % MOD;

        for (int k = 0; k < K; k++) {
            int Bk = B[k];
            ll ans1 = 0, ans2 = 0;

            // ---------- 第一部分：每个出现值恰好出现 Bk 次 ----------
            {
                // 每个值 v 的循环随机数 w[v][0..Bk-1]，总和为 0 (mod MOD)
                unordered_map<int, vector<ll>> w;
                for (int v = 1; v <= N; v++) {
                    if (cntv[v] == 0) continue;
                    if (cntv[v] >= Bk) {
                        auto& vec = w[v];
                        vec.resize(Bk);
                        ll s = 0;
                        for (int j = 0; j < Bk - 1; j++) {
                            vec[j] = rnd64();
                            s += vec[j];
                            if (s >= MOD) s -= MOD;
                        }
                        vec[Bk - 1] = (MOD - s) % MOD;
                    } else {
                        auto& vec = w[v];
                        vec.resize(cntv[v]);   // 只用到余数 0..c-1，自由随机即可
                        for (int j = 0; j < cntv[v]; j++) vec[j] = rnd64();
                    }
                }
                vector<ll> H(N + 1, 0);
                for (int i = 0; i < N; i++) {
                    int v = A[i];
                    H[i + 1] = (H[i] + w[v][rank[i] % Bk]) % MOD;
                }
                unordered_map<ll, ll> freq;
                vector<int> cnt(N + 1, 0);
                int ptr = 0;
                freq[H[0]]++;
                for (int r = 1; r <= N; r++) {
                    int v = A[r - 1];
                    cnt[v]++;
                    while (cnt[v] > Bk) {                 // 出现次数不得超过 Bk
                        int u = A[ptr];
                        cnt[u]--;
                        ll h = H[ptr];
                        if (--freq[h] == 0) freq.erase(h);
                        ptr++;
                    }
                    auto it = freq.find(H[r]);            // 数 l in [ptr, r-1] 使 H_l == H_r
                    if (it != freq.end()) ans1 += it->second;
                    freq[H[r]]++;
                }
            }

            // ---------- 第二部分：恰好含 Bk 种不同值 ----------
            {
                vector<int> cntLo(N + 1, 0), cntHi(N + 1, 0);
                int lo = 0, hi = 0;         // 左端区间 [lo, hi]
                int dLo = 0, dHi = 0;       // [lo,r-1] 与 [hi,r-1] 的不同值个数
                ll setHash = 0;             // [lo, r-1] 内不同值的集合哈希
                unordered_map<ll, ll> freq; // F_l 的频率表
                bool valid = false;         // 当前是否存在有效区间
                ll curH = -1;
                int curL = 0, curU = -1;

                auto F = [&](ll Sv, ll Hh, int idx) -> ll {
                    ll f = (Bk * Sv % MOD - Hh * idx % MOD) % MOD;
                    if (f < 0) f += MOD;
                    return f;
                };

                for (int r = 1; r <= N; r++) {
                    int v = A[r - 1];

                    // lo 窗口 [lo, r-1]：不同值个数 <= Bk，lo 最小
                    if (cntLo[v] == 0) { dLo++; setHash = (setHash + R[v]) % MOD; }
                    cntLo[v]++;
                    while (dLo > Bk) {
                        int u = A[lo];
                        cntLo[u]--;
                        if (cntLo[u] == 0) { dLo--; setHash = (setHash - R[u] + MOD) % MOD; }
                        lo++;
                    }

                    // hi 窗口 [hi, r-1]：不同值个数 >= Bk，hi 最大
                    if (cntHi[v] == 0) dHi++;
                    cntHi[v]++;
                    while (true) {
                        int u = A[hi];
                        if (dHi - (cntHi[u] == 1 ? 1 : 0) >= Bk) {
                            cntHi[u]--;
                            if (cntHi[u] == 0) dHi--;
                            hi++;
                        } else break;
                    }

                    if (dLo != Bk || dHi < Bk) {   // 不存在恰好 Bk 种的左端
                        valid = false;
                        continue;
                    }
                    if (!valid || setHash != curH) {
                        // 集合变化：用新哈希重建频率表（新下标均未入过表）
                        freq.clear();
                        for (int l = lo; l <= hi; l++) freq[F(S[l], setHash, l)]++;
                        valid = true;
                        curH = setHash;
                        curL = lo;
                        curU = hi;
                    } else {
                        for (int l = curL; l < lo; l++) {
                            ll f = F(S[l], curH, l);
                            if (--freq[f] == 0) freq.erase(f);
                        }
                        for (int l = curU + 1; l <= hi; l++) freq[F(S[l], curH, l)]++;
                        curL = lo;
                        curU = hi;
                    }
                    ll fr = F(S[r], setHash, r);
                    auto it = freq.find(fr);
                    if (it != freq.end()) ans2 += it->second;
                }
            }

            cout << ans1 << " " << ans2 << "\n";
        }
    }
    return 0;
}

复杂度分析

时间复杂度：每个测试点期望 $O(KN)$ （使用哈希表；用平衡树则为 $O(KN\log N)$ ），其中两类统计各自的每个下标均只入/出表常数次
空间复杂度： $O(N)$