原题

给定一个长度为 n 的正整数序列 a_1,a_2,...,a_n。求满足 1<=i<j<=n 且 a_i>a_j 的数对 (i,j) 数量，答案对 100 取模。

输入第一行是整数 n (1<=n<=3×10^5)；第二行是 n 个整数 a_1,...,a_n (1<=a_i<=100)。

输出一行一个整数，表示答案。

样例：

输入
3
3 2 1

输出
3

题解

MC0417 哨岗逆序对（C++17）

给定长度为 n 的序列，统计满足 i < j 且 a_i > a_j 的数对数，并对 100 取模。

从左往右扫数组。扫到 a_i 时，前面 [1,i-1] 中的逆序对早已确定，不会再受后面元素影响。此时新出现的，只可能是以 i 为右端点的 (j,i)。

对任意 j<i，(j,i) 是逆序对当且仅当 a_j>a_i。所以新增长度为 i 的贡献，就是此前出现过、值严格大于 a_i 的元素个数。值相等时不满足严格大于，不计入答案。

设 cnt[v] 为已经扫描过的元素中，值恰为 v 的个数。由于 1<=a_i<=100，当前位置的增量为

$$ \Delta_i=\sum_{v=a_i+1}^{100}cnt[v]. $$

一开始前缀为空，ans=0。每次先把 \Delta_i 加入 ans，再执行 cnt[a_i]++；顺序不能反过来，否则会把当前位置误算进前缀。第一个元素前面没有数，增量自然是 0。

每个逆序对只会在扫到它的右端点时计算一次，所以不会重复，也不会漏掉。

时间复杂度为 O(100n)=O(n)，空间复杂度为 O(100)。n<=3×10^5，可以通过。

代码

#include <array>
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    array<int, 101> cnt{};
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        int add = 0;
        for (int v = x + 1; v <= 100; ++v) {
            add += cnt[v];
        }
        ans = (ans + add) % 100;
        ++cnt[x];
    }

    cout << ans << '\n';
    return 0;
}

实现核对

cnt[v] 对应公式中的 cnt[v]；add 对应当前位置增量 \Delta_i；ans 是已经扫描前缀的逆序对数模 100。