문제 소개
문제가 되게 쉬워보이는데 무작정 덤비면 안되는 문제입니다.
문제 링크
https://codeup.kr/problem.php?id=3260
교차점의 개수
첫째 줄에 정점의 개수 $n$이 입력된다.($1<=n<=100,000$) 각 정점과 정점에는 하나의 선만 존재하며, 하나의 정점에 두 개의 선이 연결되는 경우는 없다. 둘째 줄에 $n$개의 상단 $i$번째 정점에 대한 연결된 하단 정점의 정보가 공백으로 분리되어 입력된다. 2 1 0 인 경우, 상단 $0$번 정점은 하단 $1$번과 연결, 상단 $1$번 정점은 하단 $0$번에 연결되었음을 의미한다.
codeup.kr
아이디어
일단 문제를 접근하는 "방식"은 간단합니다.
A라는 정점이 있다고 해보겠습니다.
이때, 우리가 구해야 하는 것은
A라는 정점이 선택한 정점의 번호보다 정점 A보다 큰 번호를 가진 정점이 선택한 정점의 번호가 작은 경우의 수
입니다. 그리고 A라는 정점을 모든 정점으로 확장해 생각하면 이 문제의 본질을 알 수 있습니다.
하지만 이 경우의 수를 계산하는 것이 귀찮았고 저 같은 경우는 mo's algorithm을 활용해 배열에 값들을 누적하고 개수를 세는 방식으로 해결했습니다. mo's algorithm에 대한 내용은 추후에 설명글을 올려보겠습니다.(하지만 되게 많은 GOD 분들이 설명을 많이 해주셨기 때문에 구글에 검색해보시면 많이 나옵니다.)
코드
#include <iostream>
using namespace std;
typedef long long ll;
int N,sq,ans;
ll ar[110000];
ll mo[44000];
ll cnt[110000];
ll query(int k) {
ll ret = 0;
ll mo_e = k/sq;
for(int x=0; x<=mo_e; x++) ret+=mo[x];
for(int x=(mo_e+1)*sq-1; x>k; x--) ret -= cnt[x];
return ret;
}
int main() {
cin >> N;
for(sq = 1; sq*sq <=N; sq++);
for(int x=0; x<N; x++) {
cin >>ar[x];
cnt[ar[x]]=1;
mo[ar[x]/sq]++;
}
for(int x=0; x<N; x++) {
ans += query(ar[x]-1);
cnt[ar[x]]--;
mo[ar[x]/sq]--;
}
cout<<ans;
}
mo's algorithm에 대해 공부를 하시고 나서라면 생각보다 간단한 코드일 것입니다. :)
Rmx