문제 백준 15976번 풀이 문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다. $ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다. 문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다. 누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다. 문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께..

문제 백준 2881번 풀이 나무가 존재하는 좌표를 XY좌표 나누어 관리하면 이분 탐색을 사용하여 log 복잡도로 빠르게 구할 수 있습니다. 꼭짓점에 걸쳐서 겹치는 좌표는 map을 사용하면 빠르게 빼줄 수 있습니다. 소스코드 #include using namespace std; unordered_map xAxis, yAxis; unordered_map mp; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int p; cin >> p; while (p--) { int x, y; cin >> x >> y; xAxis[x].push_back(y); yAxis[y].push_back(x); mp[x][y] = ..