1부터 N까지 for문을 돌며 구하고 싶은 답을 구한다면 O(n^2)이라는 시간복잡도가 걸리게 되어 시간초과가 납니다. 어떤식으로 풀지 고민을 하다 시간을 줄이기 위해 펜윅트리라는 알고리즘을 사용했습니다.
입력받은 배열을 이용하여 숫자의 위치를 얼마나 바꿔야하는지 알아내야 하므로 배열을 입력받을 때 해당 숫자가 몇번째에 입력받아졌는지 배열에 저장하여 그 배열을 이용하여 풀었습니다.
홀수번째 단계에서는 아직까지 고르지 않은 숫자 중 제일 작은 수를, 짝수번째 단계일때는 아직까지 고르지 않은 숫자 중 제일 큰 수를 골라 이동하는 것이므로 몇번째에 입력받았는지 저장한 배열을 이용하여 각각의 단계에서 출력해야하는 숫자의 위치를 저장해주는 배열을 하나 더 선언하여 이 문제를 해결하였습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<math.h>
#include<set>
#include<string>
#include<queue>
#define ll long long
#define num 200005
#define N 49999
using namespace std;
ll tree[num];
ll n, check[100005], arr[100005], a;
ll sum(ll i) {
ll ans = 0;
while (i > 0) {
ans += tree[i];
i -= (i & -i);
}
return ans;
}
void update(ll i, ll nn) {
while (i <= n) {
tree[i] += nn;
i += (i & -i);
}
}
int main(void) {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a);
check[a] = i;
}
a = 1;
for (int i = 1; i <= ((n + 1) / 2); i++) {
arr[a] = check[i];
arr[a + 1] = check[(n - i) + 1];
a += 2;
}
for (int i = 1; i <= n; i++)update(i, 1);
for (int i = 1; i <= n; i++) {
if (i % 2 != 0) {
if (arr[i] == 1)printf("0\n");
else printf("%lld\n", sum(arr[i] - 1));
update(arr[i], -1);
}
else {
if (arr[i] == n)printf("0\n");
else printf("%lld\n", sum(n) - sum(arr[i]));
update(arr[i], -1);
}
}
return 0;
}