# 11603: 【原1603】Count of Smaller Numbers After Self

### 题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1603

## Description

Given an integer array nums, you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums=[5,2,6,1]

• To the right of 5 there are 2 smaller elements (2 and 1).
• To the right of 2 there are 1 smaller element (1).
• To the right of 6 there are 1 smaller element (1).
• To the right of 1 there are 0 smaller element.

Return the array [2,1,1,0].

Note:

• Every element would not exceed 100000.

4
5 2 6 1

2 1 1 0

## yyong119's solution

#include <cstdio>
using namespace std;
const int MAX_N = 100005;
int n;
int nums[MAX_N], smaller[MAX_N], pos[MAX_N], result[MAX_N];

void mergesort(int *nums, int *smaller, int *pos, int l, int r) {

if (l >= r) return;
int mid = (l + r) >> 1;
mergesort(nums, smaller, pos, l, mid);
mergesort(nums, smaller, pos, mid + 1, r);
int merged[r - l + 1];
int i = l, j = mid + 1, k = 0, step = 0;
while (i <= mid || j <= r) {
if (i > mid) {
++step;
merged[k++] = pos[j++];
} else if (j > r) {
smaller[pos[i]] += step;
merged[k++] = pos[i++];
} else if (nums[pos[i]] <= nums[pos[j]]) {
smaller[pos[i]] += step;
merged[k++] = pos[i++];
} else {
++step;
merged[k++] = pos[j++];
}
}
for (int i = 0; i < r - l + 1; ++i) pos[l + i] = merged[i];
}

int main() {

scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &nums[i]);
for (int i = 0; i < n; ++i) pos[i] = i;
mergesort(nums, smaller, pos, 0, n - 1);
for (int i = 0; i < n; ++i) printf("%d ", smaller[i]);
return 0;
}