https://www.acmicpc.net/problem/2517

해결법

• 선수의 숫자 <<<<< 실력 값
  따라서 실력 순서대로 실력값을 재정의해야 할 필요가 있음
  문제에서 '선수들의 평소 실력은 다르다'는 조건 덕분에 재정의 가능!
  그렇다면 배열을 1,000,000,000개가 넘도록 만들 일이 없어진다~
  

• 시간복잡도 $O(NlogN)$인 알고리즘을 고려해야 함

  • 정렬 - 문제해결 시 입력된 순서가 중요한 정보이기 때문에.. 불가능
  • 우선순위큐 - '구간'의 데이터가 필요해서 살짝 애매..
  • 인덱스트리 - '구간'...? 이거다

• 실력을 위치정보로 하여 배열에 저장을 하면,
  입력된 실력 보다 앞에 표시된 정보(구간!)들의 합으로 답을 구할 수 있음
  예제 입력을 예시로 들면, 4번째로 달리고 있는 평소 실력이 7인 선수를 볼 때
  [ 0 1 0 1 1 0 1(나) 0] 나보다 실력 값이 작으면서, 이미 달리고 있는 사람들은 나의 앞쪽 구간의 1의 개수를 세면 됨
  

1. 인덱스 트리를 모두 0으로 초기화해둔다.
2. 달리는 순서대로 실력값에 해당하는 트리의 리프노드에 1을 update한다.
3. 1부터 (내 순서 - 1) 까지 몇명이 있는지 세어서 출력한다.

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int MAX = 2e6;
int n,powerN;
vector<pair<ll,int> > player; 
int t[MAX+1];

bool cmpIdx(pair<ll,int> &a, pair<ll,int> &b){
  return a.second<b.second;
}

void update(ll p){
  p = powerN + p -1;
  t[p] += 1;
  for(;p>1;p>>=1){
    t[p>>1] = t[p] + t[p^1];
  }
}

int query(int l, int r){
  int ret = 0;
  l = l + powerN - 1;
  r = r + powerN - 1;
  for(;l<=r;l>>=1,r>>=1){
    if(l&1) ret += t[l++];
    if(!(r&1)) ret += t[r--];
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  cin>>n;
  for(powerN=1;powerN<n;powerN<<=1);
  //player{ability, idx}
  for(int i = 1; i<=n; i++){
    ll a; cin>>a;
    player.push_back({a,i});
  }
  //실력값 재정의
  sort(player.begin(),player.end());
  for(int i = 0; i<n; i++){
    player[i].first = i+1;
  }

  //달리는 순서대로
  sort(player.begin(),player.end(),cmpIdx);
  for(int i = 0; i<n; i++){
    int idx = player[i].second;
    ll ability = player[i].first;
    update(ability);
    int weak = query(1,ability-1); //해당 선수보다 실력이 낮은 선수를 세어본다.
    cout<<idx - weak<<"\n";
  }
}

제출결과

나는 babo야.. query할 때 idx-1 써놓고 외않되........ 하고 있었다
흑흑 어쨌든 해피엔딩