颜色与幸运数字 - 题解

标签与难度

标签: 离线处理, 树状数组, Fenwick Tree, 扫描线, 数据结构, 贡献法难度: 2200

题目大意喵~

你好呀，指挥官！这道题是小蓝在考验小灰灰呢，真可爱~ 事情是这样的：

河边有 n 颗排成一排的小石子，每颗石子都有一个颜色 c_i。小蓝的幸运数字是 k。

然后，小蓝会提出 m 个问题。每个问题都会指定一个区间 [l, r]，问的是在这个区间里，所有 恰好出现了 k 次 的颜色，它们的颜色值加起来的总和是多少？

比如说，如果 k=2，区间里有颜色 5 (出现了2次)，颜色 8 (出现了2次)，颜色 3 (出现了1次)。那么答案就是 5 + 8 = 13 啦！

我们要做的就是帮小灰灰回答所有 m 个问题，喵~

输入:

第一行是三个整数 n, m, k。
第二行是 n 个整数，代表 n 颗石子的颜色 c_1, c_2, ..., c_n。
接下来 m 行，每行两个整数 l, r，代表一个查询。

输出:

对每个查询输出一行，表示答案。

解题思路分析

这道题的数据范围很大呢， $N$ 和 $M$ 都可以达到 $10^6$ 。如果我们对每个查询都傻乎乎地跑去区间 [l, r] 里数一遍颜色，那复杂度就是 $O(M \times N)$ ，肯定会超时的说！(ﾉ*ФωФ)ﾉ

当题目里的查询不涉及修改，并且可以不按顺序回答时，我们就可以请出强大的 离线处理 大法师！其中一个特别好用的技巧叫做 扫描线。

我们可以把查询 (l, r) 看作是二维平面上的一个点。但是直接处理二维问题太麻烦了，我们不如把它降到一维来解决！

扫描线的魔法！

我们可以把所有查询按照它们的 右端点 r 进行排序（或者分组）。然后，我们用一根“扫描线”从左到右扫过整个石子序列，也就是让 r 从 1 遍历到 n。

当我们的扫描线移动到位置 r 时，我们就处理所有右端点恰好是 r 的查询。

那么问题来了，当扫描线在 r 时，我们怎么快速回答查询 (l, r) 呢？

贡献法的思考

我们换个角度想问题，喵~ 不要去想“对于一个查询，它的答案是多少”，而是想“对于一种颜色，它在什么时候会产生贡献？”

一种颜色 C 对查询 (l, r) 产生贡献，当且仅当它在 c[l...r] 这个区间里不多不少，正好出现了 k 次。

假设当我们的扫描线移动到 r 时，颜色 C = c[r] 是它在整个序列中第 t 次出现。我们把 C 出现过的位置记下来，分别是 $p_1, p_2, \dots, p_t=r$ 。

为了让 C 在 c[l...r] 中出现 k 次，这个区间的左端点 l 必须满足什么条件呢？它必须包含最新的 k 个 C，也就是 $p_{t-k+1}, \dots, p_t$ ，但又不能包含更早的那个，也就是 $p_{t-k}$ 。

所以 l 必须满足：

p_{t-k} < l \le p_{t-k+1}

这意味着，当扫描线在 r 时，对于颜色 c[r]，它会对所有左端点 l 在区间 $(p_{t-k}, p_{t-k+1}]$ 的查询 (l, r) 产生 c[r] 的贡献！

用树状数组维护贡献

我们发现，当扫描线在 r 时，我们需要处理的是一系列对 l 的区间 (p_{t-k}, p_{t-k+1}]$ 增加一个值的操作，并且要快速查询某个 l` 上的总和。

这正是 树状数组 (Fenwick Tree) 的拿手好戏呀！我们可以用一个树状数组 bit，bit[i] 存储的是在左端点为 i 的位置上，所有颜色的总贡献值。

区间增加: 要给 l \in [x, y] 区间的所有位置都加上 val，我们可以执行 bit.add(x, val) 和 bit.add(y + 1, -val)。
单点查询: 查询左端点为 l 的总贡献，就是求树状数组的前缀和 bit.query(l)。

算法流程总结

好啦，把所有思路串起来，我们的算法就诞生了，喵~

预处理:
- 用一个 vector<int> color_positions[MAX_COLOR] 来存储每种颜色出现的所有位置。为了方便处理边界，我们可以在每个 vector 的最前面放一个 0 作为哨兵。
- 用一个 vector<pair<int, int>> queries_by_r[N+1] 来存储所有查询。queries_by_r[r] 存放所有右端点为 r 的查询，pair 中存储左端点 l 和原始查询的编号 idx。
扫描与计算:
- 初始化一个大小为 N+1 的树状数组 bit，和一个 ans 数组来存答案。
- 用一个 current_occurrence_count 数组来记录扫描过程中每种颜色已经出现了多少次。
- 开始扫描！让 r 从 1 遍历到 n： a. 处理当前石子 c[r]:
  - 令 color = c[r]，这是它第 t = ++current_occurrence_count[color] 次出现。
  - p_t 就是当前位置 r。p_{t-k} 和 p_{t-k+1} 可以从 color_positions[color] 中查到。
  - 更新贡献: * 如果 t > k，说明 color 在上一步（当它出现 t-1 次时）产生的贡献已经失效了。旧的贡献范围是 $(p_{t-1-k}, p_{t-k}]$ 。我们需要撤销这个贡献，即在这个 l 区间减去 color。 * 如果 t >= k，说明 color 现在产生了一个新的贡献。新的贡献范围是 $(p_{t-k}, p_{t-k+1}]$ 。我们在这个 l 区间加上 color。 b. 回答查询:
  - 遍历 queries_by_r[r] 中的所有查询 (l, idx)。
  - 对于每个查询，它的答案就是 bit.query(l)。将结果存入 ans[idx]。
输出结果:
- 按顺序输出 ans 数组中的所有答案。

这样，我们通过一次扫描就优雅地解决了所有问题，时间复杂度是 $O((N+M)\log N)$ ，完全可以接受，太棒了喵！

代码实现

这是我根据上面的思路，精心重构的代码哦~ 希望能帮到你，喵！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1e6 + 10;

// 使用 long long 防止求和时溢出
using ll = long long;

int n, m, k;
int colors[MAXN];
ll answers[MAXN];

// 我们的主角：树状数组 (Fenwick Tree)
ll bit[MAXN];

// 在位置 x 增加 val
void add(int x, ll val) {
    for (; x <= n; x += x & -x) {
        bit[x] += val;
    }
}

// 查询 [1, x] 的前缀和
ll query(int x) {
    ll sum = 0;
    for (; x > 0; x -= x & -x) {
        sum += bit[x];
    }
    return sum;
}

// 离线存储查询，first 是左端点 l, second 是查询的原始编号
vector<pair<int, int>> queries_by_r[MAXN];

// 存储每种颜色出现的位置
vector<int> color_positions[MAXN];

// 记录扫描时每种颜色已经出现了多少次
int current_occurrence_count[MAXN];

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i) {
        cin >> colors[i];
    }
    
    // 预处理颜色位置
    // 在每个颜色的位置列表前加一个 0，作为哨兵，方便处理边界情况
    for (int i = 0; i < MAXN; ++i) {
        color_positions[i].push_back(0);
    }
    for (int i = 1; i <= n; ++i) {
        color_positions[colors[i]].push_back(i);
    }

    // 离线存储查询
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        queries_by_r[r].push_back({l, i});
    }

    // --- 开始扫描线 ---
    for (int r = 1; r <= n; ++r) {
        int current_color = colors[r];
        current_occurrence_count[current_color]++;
        int t = current_occurrence_count[current_color];

        // 获取颜色出现的位置，p_t, p_{t-k} 等
        // 由于 vector 下标从 0 开始，第 t 次出现的位置是 color_positions[...][t]
        
        // 当一个颜色出现次数达到 k 次，它就开始产生贡献
        if (t >= k) {
            int pos_t_minus_k = color_positions[current_color][t - k];
            int pos_t_minus_k_plus_1 = color_positions[current_color][t - k + 1];
            // 对于 l 在 (pos_{t-k}, pos_{t-k+1}] 的查询，颜色 current_color 贡献了 k 次
            // 我们在树状数组上给区间 [pos_{t-k} + 1, pos_{t-k+1}] 加上 current_color
            add(pos_t_minus_k + 1, current_color);
            add(pos_t_minus_k_plus_1 + 1, -current_color);
        }

        // 当一个颜色出现次数超过 k 次 (即达到 k+1 次)，
        // 它之前作为“恰好k次”的贡献就失效了
        if (t > k) {
            int pos_t_minus_k_minus_1 = color_positions[current_color][t - k - 1];
            int pos_t_minus_k = color_positions[current_color][t - k];
            // 之前 l 在 (pos_{t-k-1}, pos_{t-k}] 的查询，color 贡献了 k 次
            // 现在这个贡献不再有效，需要撤销
            // 我们在树状数组上给区间 [pos_{t-k-1} + 1, pos_{t-k}] 减去 current_color
            add(pos_t_minus_k_minus_1 + 1, -current_color);
            add(pos_t_minus_k + 1, current_color);
        }

        // 回答所有右端点为 r 的查询
        for (auto const& query_pair : queries_by_r[r]) {
            int l = query_pair.first;
            int query_idx = query_pair.second;
            answers[query_idx] = query(l);
        }
    }

    // 按顺序输出所有答案
    for (int i = 0; i < m; ++i) {
        cout << answers[i] << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O((N+M)\log N)$
- 预处理颜色位置和存储查询需要 $O(N+M)$ 的时间。
- 主循环（扫描线）遍历 r 从 1 到 n，是 $O(N)$ 。
- 在循环中，每次对树状数组的更新操作是 $O(\log N)$ 。每个位置 r 只会触发常数次更新。总共是 $O(N \log N)$ 。
- 回答查询时，总共有 M 个查询，每个查询在树状数组上花费 $O(\log N)$ 。总共是 $O(M \log N)$ 。
- 所以总的时间复杂度是 $O(N+M+N\log N+M\log N) = O((N+M)\log N)$ 。
空间复杂度: $O(N+M)$
- colors, bit, answers, current_occurrence_count 数组都需要 $O(N)$ 或 $O(M)$ 的空间。
- color_positions 存储了所有 N 个石子的位置，总空间是 $O(N)$ 。
- queries_by_r 存储了所有 M 个查询，总空间是 $O(M)$ 。
- 所以总的空间复杂度是 $O(N+M)$ 。

知识点总结

这道题是一个非常经典的将数据结构和算法思想结合的例子呢！

离线处理 (Offline Processing): 当查询可以不按顺序回答时，可以先读入所有查询，重新组织它们的处理顺序，以达到优化的目的。这是一种化被动为主动的强大思维！
扫描线 (Sweep-Line Algorithm): 将二维或高维问题降维处理的利器。通过移动一根“线”，将静态的问题转化为动态的过程，在每个步骤上维护信息并回答相关的查询。
贡献法 (Contribution Method): 解决计数或求和问题时，从考虑“每个查询的答案”转为考虑“每个元素对哪些查询有贡献”，往往能简化问题。
树状数组 (Fenwick Tree): 高效维护序列前缀和的数据结构。在这里，我们巧妙地利用它实现了“区间加，单点查”的功能，完美契合了扫描线算法的需求。

通过这道题，我们可以深刻体会到，面对复杂的问题，转换思考角度和运用合适的工具是多么重要，喵~ (ฅ'ω'ฅ)

颜色与幸运数字 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

扫描线的魔法！ ​

贡献法的思考 ​

用树状数组维护贡献 ​

算法流程总结 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​