[KOI'18] XCorr

 문제는 여기에서 확인 가능하다.

---

주어진 두 수 $a$, $b$에 대해서 $\sum_{a \leq t \leq b} XCorr(t)$를 계산할 때, $x_i$와 곱해지는 $y_j$들을 생각하자. $p_i = max(0, i+a), q_i = min(n-1, i+b)$라고 하면 $x_i$와 곱해지는 $y_j$들은 $y_{p_i}, y_{p_1+1}, ..., y_{q_i}$가 됨을 알 수 있다. 따라서 구하고자 하는 것을 다음과 같이 바꿀 수 있다.

$$\sum_{a \leq t \leq b} XCorr(t) = \sum_{i = 0}^{n-1} {\sum_{j = p_i}^{q_i} {x_i y_i}}$$

 이때 $\sum_{j = p_i}^{q_i} {y_i}$는 전처리를 통해서 $O(\log M)$에 구할 수 있으므로, 전체 시간복잡도 $O(N \log M)$에 답을 구할 수 있다.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int lld;
typedef pair<int, lld> pil;
 
int N, M;
lld presum[300005], Xi[300005], X[300005], Yi[300005], Y[300005];
lld rst, a, b;
 
void input() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> Xi[i] >> X[i];
    cin >> M;
    for(int i = 1; i <= M; i++) cin >> Yi[i] >> Y[i];
    cin >> a >> b;
}
 
void f() {
    for(int i = 1; i <= M; i++) presum[i] = Y[i] + presum[i-1];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    input();
    f();
    for(int i = 1; i <= N; i++) {
        int tmp = presum[upper_bound(Yi+1, Yi+M+1, Xi[i] + b) - Yi - 1] - presum[lower_bound(Yi+1, Yi+M+1, Xi[i]+a) - Yi - 1];
        rst += tmp*X[i];
    }
    cout << rst;
    return 0;
}