백준 15976번, 한국정보올림피아드 2018년 고등부 2번, XCorr 풀이

문제

백준 15976번

풀이

문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다.

$ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다.

 

문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다.

 

누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다.

문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께 처리하면 됩니다.)

 

그리고, 문제에서 구해야하는 $ S(a, b) $에서 수열 $ X_{i} $에 대해 더해지는 수열 $ Y $의 구간은 $ i + a $부터 $ i + b $입니다. (단, $ a <= b $)

 

또한, 누적합 배열 $ sum $에서 필요한 구간의 합을 구하려면 구간 $ i + a $와 $ i + b $를 배열 $ sum $에 대해서 이분 탐색을 사용하여 빠르게 처리할 수 있습니다. 이분 탐색을 사용하면 각 $ X_{i} $에 대해 $ O(logM) $의 시간 복잡도를 가집니다.

 

한편, 수열 $ X $의 길이는 $ N $이므로 전체 시간 복잡도는 $ O(NlogM) $이 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
vector<pii> x, y_sum;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		x.emplace_back(a, b);
	}

	int m;
	cin >> m;
	y_sum.resize(m + 1);
	y_sum[0] = {-1, 0};
	for (int i = 1; i <= m; i++) {
		cin >> y_sum[i].first >> y_sum[i].second;
		y_sum[i].second += y_sum[i - 1].second;
	}

	ll a, b, ans = 0;
	cin >> a >> b;
	--a;
	for (const auto &p : x) {
		ans += p.second * (
				min(y_sum.begin() + m, max(y_sum.begin(), lower_bound(y_sum.begin(), y_sum.end(), pii{p.first + b, 1e9}) - 1))->second
				- max(y_sum.begin(), lower_bound(y_sum.begin(), y_sum.end(), pii{p.first + a, 1e9}) - 1)->second
		);
	}

	cout << ans;
}