1. 从统计数字问题看大数据量计数的挑战

第一次看到NOIP2007提高组的统计数字题目时，我完全被它的数据规模震撼到了。题目要求统计2×10^5个数字的出现次数，每个数字的范围竟然能达到10^9！这让我想起去年带队时，有个学生直接开了个10^9大小的数组，结果程序直接崩溃的尴尬场景。

这类问题的核心矛盾在于：数据总量大但种类有限。具体到这道题，虽然数字范围达到10^9，但不相同的数字不超过10^4个。这就好比要在太平洋里统计所有鱼类的数量——海域面积虽大（数据范围广），但鱼的种类相对有限（数据种类少）。传统计数排序在这里完全失效，因为开一个10^9大小的数组需要约3814MB内存，远超题目64MB的限制。

在实际竞赛中，这类问题通常会设置三个关键限制条件：

• 数据总量n（如2×10^5）
• 数据范围（如1到10^9）
• 不同数据的种类数m（如不超过10^4）

理解这些限制非常重要，它们直接决定了我们可以采用哪些算法策略。比如当n=2×10^5，m=10^4时，O(nlogn)的算法完全可接受，但O(n^2)的算法就会超时。这也是为什么我们需要掌握多种计数方法，针对不同场景灵活选择。

2. 基础解法：排序+遍历的经典思路

2.1 排序后线性扫描的实现细节

我最推荐的入门解法就是先排序后统计。这个方法虽然简单，但包含了很多值得注意的细节。以题目样例为例，输入8个数：2 4 2 4 5 100 2 100。排序后得到2 2 2 4 4 5 100 100。

统计时的核心技巧是维护两个变量：当前数字num和计数器ct。初始化时，num设为第一个数字a[1]，ct=1。然后从第二个数字开始遍历：

• 如果a[i]==num，ct加1
• 否则，输出num和ct，然后重置num=a[i]，ct=1

这里有个易错点：遍历结束后，最后一个数字的统计结果还没输出，需要在循环外补上一次输出。很多同学都在这里丢过分，我自己第一次写也栽过跟头。

sort(a+1, a+1+n);
num = a[1]; ct = 1;
for(int i = 2; i <= n; ++i) {
    if(a[i] == num) ct++;
    else {
        cout << num << ' ' << ct << endl;
        num = a[i]; ct = 1;
    }
}
cout << num << ' ' << ct << endl; // 不要忘记最后这个输出！

2.2 复杂度分析与适用场景

这个解法的时间复杂度主要由排序决定。使用C++的sort函数（通常是快速排序），平均时间复杂度是O(nlogn)。对于n=2×10^5的数据量，这个复杂度完全在可接受范围内。

但要注意，这个方法的空间复杂度是O(n)，因为需要存储所有输入数据。在极端情况下，如果n非常大（比如10^7级别），可能会遇到内存问题。不过对于NOIP/NOI级别的题目，这个解法通常已经足够。

这个方法的优势在于：

• 实现简单，不易出错
• 不需要额外数据结构知识
• 适用于大多数编程语言

我建议在时间紧张的比赛环境中，如果没有更好的思路，可以优先采用这个解法，至少能保证基础分数。

3. 进阶策略：离散化技术的精妙运用

3.1 离散化的原理与实现步骤

当数据范围很大但种类较少时，离散化就像变魔术一样神奇。它的核心思想是把稀疏的大范围数据映射到紧凑的小范围索引上。比如把数值{500, 2000000, 1000000000}映射为{0,1,2}。

具体实现分为三步：

1. 排序：将所有数字排序
2. 去重：使用unique函数去除重复元素
3. 映射：通过二分查找确定每个数字的离散化索引

C++中可以利用STL优雅地实现：

vector<int> t(a+1, a+1+n); // 复制原始数组
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end()); // 去重
for(int i = 1; i <= n; ++i) 
    d[i] = lower_bound(t.begin(), t.end(), a[i]) - t.begin();

3.2 离散化后的计数技巧

离散化完成后，所有数字都被映射到0到m-1的范围内（m是不重复数字的个数）。这时就可以开一个大小为m的数组c来计数了：

int c[MAX_M] = {0}; // MAX_M=1e4+5
for(int i = 1; i <= n; ++i)
    c[d[i]]++;

输出时需要还原原始数字，这就要用到我们之前保存的t数组：

for(int i = 0; i < t.size(); ++i)
    if(c[i] > 0)
        cout << t[i] << ' ' << c[i] << endl;

3.3 离散化方法的优势与局限

离散化的最大优势是大幅减少了内存使用。原本需要处理10^9的范围，现在只需要处理10^4的范围，内存消耗从GB级降到了KB级。

但离散化也有其局限性：

• 需要额外的O(n)空间存储离散化结果
• 实现相对复杂，容易出错
• 修改操作不便（适合静态数据）

在去年的NOI网络同步赛中，就有一道类似的题目，很多选手因为离散化实现不完整（忘记去重或映射错误）而丢分。建议平时多练习这类题型，熟能生巧。

4. STL map的优雅解法

4.1 map容器的自动排序特性

C++的map容器简直是这类问题的"瑞士军刀"。它基于红黑树实现，会自动按照键值排序，而且内存使用非常高效。对于统计数字问题，我们可以用map<int,int>，其中key是数字，value是该数字出现的次数。

map<int, int> mp;
for(int i = 1; i <= n; ++i) {
    cin >> a;
    mp[a]++;
}

这样短短几行代码就完成了所有统计工作！map会自动处理新数字的插入和已有数字的计数增加。

4.2 遍历输出的注意事项

当需要输出结果时，map已经帮我们按key排好序了，直接遍历即可：

for(auto &p : mp)
    cout << p.first << ' ' << p.second << '\n';

这里有几个细节值得注意：

1. 使用auto&避免不必要的拷贝
2. map的遍历本身就是按键升序的
3. 输出格式要严格符合题目要求（空格和换行）

4.3 复杂度对比与选择建议

map解法的时间复杂度是O(nlogm)，其中m是不重复数字的个数。虽然理论复杂度比排序法略好（logm vs logn），但实际上由于map操作的开销较大，在小数据量时可能反而比排序法慢。

我做过实测对比：

• 当n=1e5，m=1e4时，排序法约150ms，map法约200ms
• 当n=1e5，m=1e2时，排序法约150ms，map法约120ms

因此建议：

• 当m接近n时（数据重复少），优先用排序法
• 当m远小于n时（数据重复多），考虑用map
• 当需要支持动态插入时，只能用map

5. 实战中的优化技巧与常见陷阱

5.1 输入输出的效率优化

在处理大数据量时，IO经常成为性能瓶颈。我有一次在洛谷提交时，就因为没优化IO导致TLE（时间超出限制）。两个实用技巧：

1. 在C++中使用更快的输入方式：

ios::sync_with_stdio(false);
cin.tie(0);

2. 避免使用endl，改用'\n'：

cout << num << ' ' << ct << '\n'; // 比endl快很多

5.2 内存使用的精细控制

虽然现代计算机内存很大，但在算法竞赛中，内存限制往往比时间限制更严格。一些节省内存的技巧：

• 使用vector代替静态数组，按需分配
• 对于bool数组，可以用bitset
• 离散化时，原始数组和离散化数组可以复用

5.3 边界情况的全面考虑

这类题目常见的边界情况包括：

• 所有数字都相同
• 每个数字只出现一次
• 最大和最小边界值
• 空输入（虽然题目通常保证n≥1）

建议编写代码时先考虑这些特殊情况，可以避免很多失分。