题解 | 左侧严格小于计数

#include <stdio.h>

int main() {
    int n;
    scanf("%d\n", &n);

    int shuzu[n];
    for (int i = 0; i < n; i++){
        int a;
        scanf("%d", &a);
        shuzu[i] = a;
    }

    for (int i = 0; i < n; i++){
        int sum = 0;
        for (int j = i; j >= 0; j--){
            if (shuzu[j] < shuzu[i]){
                sum++;
            }
        }
        printf("%d ", sum);
    }
    return 0;
}


//更高效的解法
// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>

// #define MAX_N 100010

// int tree[MAX_N];

// void update(int index, int value, int n) {
//     while (index <= n) {
//         tree[index] += value;
//         index += index & -index;
//     }
// }

// int query(int index) {
//     int sum = 0;
//     while (index > 0) {
//         sum += tree[index];
//         index -= index & -index;
//     }
//     return sum;
// }

// int main() {
//     int n;
//     scanf("%d", &n);
    
//     int arr[n];
//     for (int i = 0; i < n; i++) {
//         scanf("%d", &arr[i]);
//     }
    
//     // 初始化树状数组
//     memset(tree, 0, sizeof(tree));
    
//     for (int i = 0; i < n; i++) {
//         // 查询比arr[i]小的数个数
//         int count = query(arr[i] - 1);
//         printf("%d ", count);
//         // 更新树状数组
//         update(arr[i], 1, MAX_N);
//     }
    
//     return 0;
// }