蚁人跟蚂蚁军团一起作战，完成过很多了不起的任务。 但是训练蚂蚁军团倒是一个不小的难题，随着军团的壮大，已经有了不到百万只蚂蚁服役；为了便于管理，蚁人先让他们排成一个 � × � ( 1 ≤ � , � ≤ 1 0 6 , � × � ≤ 1 0 6 ) n×m(1≤n,m≤10 6 ,n×m≤10 6 ) 方阵。 其中每个蚂蚁都有自己的武力值 � ( 1 ≤ � ≤ 1000 ) x(1≤x≤1000)，那么问题来了，每一列有多少只蚂蚁的武力值跟这一列最后一个蚂蚁的武力值相等。（注意：统计的数据包含这一列的最后一只蚂蚁） 如果能回答出来蚁人可以带你去体验一次量子领域（如果你不害怕回不来的话）。 输入格式 第一行包含两个正整数 � , � n,m； 接下来 � n 行每行包含 � m 个整数表示这一行每个蚂蚁的武力值。 输出格式 输出包含 � m 个空格隔开的整数表示每一列多少只蚂蚁的武力值跟这一列最后一个蚂蚁的武力值相等。c++

以下是 C++ 代码实现：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e6 + 10;

int n, m;
int a[N], cnt[N];
vector<int> col[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> a[(i - 1) * m + j];
            col[j].push_back(a[(i - 1) * m + j]);
        }

    for (int j = 1; j <= m; j ++ )
    {
        sort(col[j].begin(), col[j].end());
        int last = col[j][0], c = 1;
        for (int i = 1; i < n; i ++ )
        {
            if (col[j][i] == last) c ++ ;
            else
            {
                cnt[last] += c;
                c = 1, last = col[j][i];
            }
        }
        cnt[last] += c;
    }

    for (int i = 1; i <= m; i ++ ) cout << cnt[a[(n - 1) * m + i]] << ' ';

    return 0;
}

思路解析：

题目需要我们求每一列中有多少只蚂蚁的武力值与该列最后一只蚂蚁的武力值相等。我们可以将这个问题转换为求每个武力值在多少个位置出现。这样，我们就可以在 O(mnlogn) 的时间复杂度内解决这个问题。

具体实现时，我们可以将每一列中的所有蚂蚁的武力值存入一个 vector 中，然后对这个 vector 进行排序，再遍历一遍 vector 统计每个武力值在其中出现的次数。最后，我们只需要在原矩阵中取出每一列的最后一个元素，利用上述统计结果即可求出答案。

时间复杂度分析：

对于每一列，我们需要对其中的所有元素进行排序，时间复杂度为 O(nlogn)。总共有 m 列，所以总时间复杂度为 O(mnlogn)。