2517

처음에 바로 BIT로 풀어야지 했다가 

정수의 범위가 1000000000까지인걸 단순히 BIT로 접근해선 안되겠음을 깨달았다.

이전까지 탐색한 정보들을 Heap에 넣어둘까 하다가 최악의 경우가 O(n*n)이라 별 소용이 없음을 생각하고 다른 방법을 강구...

그러다가 어차피 선수의 수가 500000이하니까 1~1000000000을 1~500000로 좁히는 방법을 생각했다.

방법은 1~1000000000의 data들을 정렬해서 그 data의 index값을 BIT에 쓰는 방법이다.

해당 index 값을 찾는 과정은 이진 탐색이니까 O(log(500000))으로 확 준다.

그러면 BIT에 index값까지의 합을 확인하고 현재까지 탐색한 선수의 수를 빼주고

그 index에 1만큼 update한다. 이 과정은 O(logN)

시간복잡도를 O(NlogN)으로 줄일 수 있었다.

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int MAX=1111111; int tree[MAX]; int data[MAX]; int index_data[MAX]; int read(int idx) { int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val) { while(idx <= MAX) { tree[idx] += val; idx += (idx & -idx); } } int main() { int n, find; scanf("%d", &n); for(int idx=1; idx<=n; idx++) { scanf("%d", &data[idx]); index_data[idx]=data[idx]; } sort(index_data+1, index_data+n+1); for(int piv=1; piv<=n; piv++) { find=data[piv]; int lo=1, hi=n; int mid=(lo+hi)/2; while(lo<=hi) { if(index_data[mid]==find) break; else if(index_data[mid]>find) hi=mid-1; else lo=mid+1; mid=(hi+lo)/2; } printf("%d\n", piv-read(mid)); update(mid,1); } return 0; }