BOJ 5419 North-Western Winds

x 좌표는 오름차순, y 좌표는 내림차순으로 정렬.

정렬된 순으로 진행하면서 이전까지 기록한 y 좌표가 크거나 같은 것의 개수를 센다.

즉, 범위 안의 y 좌표를 효과적으로 세야하니까 segment tree 나 Fenwick tree 를 쓴다.

 

먼저 Fenwick tree 부터

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int sz;
pair<int,int> arr[75000];
int cpy[75000], bits[75001];

void upd(int p){
    for(;p<=sz;p+=p&-p)
        bits[p]++;
}

ll qry(int p){
    ll ans=0;
    for(;p>0;p&=p-1)
        ans+=bits[p];
    return ans;
}

void solve(){
    int n; scanf("%d", &n);
    for(int i=1;i<=n;i++) bits[i]=0;
    
    for(int i=0;i<n;i++){
        int a,b; scanf("%d%d",&a,&b);
        arr[i].first=a, arr[i].second=b;
        cpy[i]=b;
    }
    
    sort(arr, arr+n, [](pair<int,int> &a, pair<int,int> &b){
        if(a.first==b.first) return a.second>b.second;
        return a.first<b.first;
    });
    
    sort(cpy,cpy+n);
    sz=unique(cpy,cpy+n)-cpy;
    
    ll ans=0;
    for(int i=0;i<n;i++){
        int p=lower_bound(cpy, cpy+sz, arr[i].second)-cpy;
        ans+=i-qry(p);
        upd(p+1);
    }
    printf("%lld\n", ans);
}

int main(){
    int T; scanf("%d",&T);
    while(T--) solve();
}

 

segment tree 귀찮지만 간간히 쓰자.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

pair<int,int> arr[75000];
int cpy[75000], tree[300000];

void upd(int l,int r,int node,int p){
    if(p<l || r<p) return;
    if(l==r){
        tree[node]++;
        return;
    }
    
    int mid=l+r>>1;
    upd(l,mid,2*node,p), upd(mid+1,r,2*node+1,p);
    tree[node]=tree[2*node]+tree[2*node+1];
}

ll qry(int l,int r,int node,int ql){
    if(r<ql) return 0;
    if(ql<=l) return tree[node];
    
    int mid=l+r>>1;
    return qry(l,mid,2*node,ql)+qry(mid+1,r,2*node+1,ql);
}

void solve(){
    int n; scanf("%d", &n);
    for(int i=0;i<4*n;i++) tree[i]=0;
    
    for(int i=0;i<n;i++){
        int a,b; scanf("%d%d",&a,&b);
        arr[i].first=a, arr[i].second=b;
        cpy[i]=b;
    }
    
    sort(arr, arr+n, [](pair<int,int> &a, pair<int,int> &b){
        if(a.first==b.first) return a.second>b.second;
        return a.first<b.first;
    });
    
    sort(cpy,cpy+n);
    int sz=unique(cpy,cpy+n)-cpy;
    
    ll ans=0;
    for(int i=0;i<n;i++){
        int p=lower_bound(cpy, cpy+sz, arr[i].second)-cpy;
        ans+=qry(0, sz-1, 1, p);
        upd(0, sz-1, 1, p);
    }
    printf("%lld\n", ans);
}

int main(){
    int T; scanf("%d",&T);
    while(T--) solve();
}