백준 7493 - Collisions

문제 링크 : https://www.acmicpc.net/problem/7493

문제를 읽고나면

공들의 충돌이 끝나는 상황은
각 공들의 속도가 오름차순으로 정렬된 때임을 알 수 있다

즉 초기상황에서 시작하여
오름차순으로 정렬될 때까지의 공들의 충돌횟수를 구하면 된다

공의 좌표는 배열에서의 idx
공의 속도는 idx에 들어잇는 값 으로 한다음에

충돌 횟수만 구하면 되니깐
처음주어진 좌표를 압축해서 재정의한다음

inversion counting을 구하면 된다.
머지소트트리나 세그먼트 트리로 하면되는데

나는 세그먼트트리로했다..

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
int N;
vector<pair<int,ll>> arr;
int segtree[200001*4];
int query(int start,int end,int node,int left,int right){
    if(right<start||left>end){
        return 0;
    }
    if(left<=start&&end<=right){
        return segtree[node];
    }
    int mid=(start+end)/2;
    return query(start,mid,node*2,left,right)+
    query(mid+1,end,node*2+1,left,right);
}
void update(int start,int end,int node,int lidx){
    if(end<lidx||start>lidx){
        return ;
    }
    segtree[node]+=1;
    if(start==end){
        return ;
    }
    int mid=(start+end)/2;
    update(start,mid,node*2,lidx);
    update(mid+1,end,node*2+1,lidx);
}

int main(){
    cin>>N;
    vector<ll> temp;
    for(int i=0;i<N;i++){
        int speed;
        ll coordinate;
        cin>>coordinate>>speed;
        arr.push_back({speed,coordinate});
        temp.push_back({coordinate});
    }
    sort(temp.begin(),temp.end());
    vector<int> temp2;
    for(int i=0;i<N;i++){
        int idx = lower_bound(temp.begin(),temp.end(),arr[i].second)-temp.begin();
        temp2.push_back(idx);
    }
    for(int i=0;i<N;i++){
        arr[i].second=temp2[i];
    }
    sort(arr.begin(),arr.end());
    vector<int> arr2;
    for(int i=0;i<arr.size();i++){
        arr2.push_back(arr[i].second);
    }
    long long ans=0;

    for(int i=0;i<N;i++){
        ans+=query(0,N-1,1,arr2[i],N-1);
    
        update(0,N-1,1,arr2[i]);
    }
    cout<<ans;
}